[알고리즘/프로그래머스] 그리디 - 조이스틱

탐욕법(Greedy) > 조이스틱 

(개인적으로 어려웠음)

 

코딩테스트 연습 - 조이스틱

 

만들고자 하는 이름 name이 매개변수로 주어질 때,

이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수 만들기

 

---

실패한 코드

 

아래의 코드는 테스트케이스 11번이 틀림

--> "ABAAAAAAAAABB" 일 때 7이 출력되야 하는데 15가 출력됨

한 방향으로 가는 것만이 아니라 2번째 B까지 갔다가 다시 돌아가는 것이 빠르기 때문에 출력값이 다름

 

def solution(name):
    make_A = list(map(lambda x: ord(name[x]) - ord('A'), range(len(name))))
    make_Z = list(map(lambda x: ord('Z') - ord(name[x]) + 1, range(len(name))))
    make_name = list(map(lambda x: make_A[x] if make_A[x] < make_Z[x] else make_Z[x], range(len(name))))
    count_f = 0
    count_l = 0
    
    while len(make_name) > 1 and make_name[1] == 0:
        count_f+=1
        make_name.pop(1)
    while len(make_name) > 2 and make_name[-2] == 0:
        count_l+=1
        make_name.pop(-2)
    max_count = count_f if count_f > count_l else count_l

    return sum(make_name)+len(name)-1-max_count

 

다시 수정한 코드

 

def solution(name):
    make_name = list(map(lambda x: ord(name[x]) - ord('A')
                         if ord(name[x]) - ord('A') < ord('Z') - ord(name[x]) + 1 
                         else ord('Z') - ord(name[x]) + 1, range(len(name))))
    
    A_str = []
    A_list = []
    for i in range(len(name)):
        if name[i] == 'A':
            A_str.append('A')
            if i == len(name) - 1:
                A_list.append(len(A_str))
        else:
            if A_str:
                A_list.append(len(A_str))
            A_list.append(0)
            A_str = []
    
    l_c = A_list.index(max(A_list))-1 if A_list.index(max(A_list)) != 0 else 0 
    r_c = len(name) - (A_list.index(max(A_list))+max(A_list))
    min_count = min([len(name)-1, l_c*2+r_c, r_c*2+l_c])
    
    return sum(make_name)+min_count

 

- make_name list : 각 알파벳을 가장 작게 움직이면서 만들 수 있는 수

    make_name = list(map(lambda x: ord(name[x]) - ord('A')
                         if ord(name[x]) - ord('A') < ord('Z') - ord(name[x]) + 1 
                         else ord('Z') - ord(name[x]) + 1, range(len(name))))

 

- A를 기준으로 리스트 분할할 때 A가 연속되는 문자열의 크기로 A_list 리스트를 만들어 준다.

예시 - "ABAAAAAAAAABB" --> "A(1)B(0)AAAAAAAAA(9)B(0)B(0)" -->  [1, 0, 9, 0, 0]

 

    A_str = []
    A_list = []
    for i in range(len(name)):
        if name[i] == 'A':
            A_str.append('A')
            if i == len(name) - 1:
                A_list.append(len(A_str))
        else:
            if A_str:
                A_list.append(len(A_str))
            A_list.append(0)
            A_str = []

 

- A_list 에서 가장 길게 연속 된 A의 개수를 구한다.

- 그 수를 기준으로 왼쪽으로 움직여야 하는 개수 / 오른쪽으로 움직여야 하는 개수를 구해준다.

(아래의 경우의 수 같은 것을 위해 코드를 이렇게 작성)

예시 - "ABAAAAAAAAABB" --> "AB(*)AAAAAAAAAB(*)B" -->  l_c = 1, r_c = 2

- 움직일 수 있는 경우의 수 중 가장 작은 값을 구한다.

    l_c = A_list.index(max(A_list))-1 if A_list.index(max(A_list)) != 0 else 0 
    r_c = len(name) - (A_list.index(max(A_list))+max(A_list))
    min_count = min([len(name)-1, l_c*2+r_c, r_c*2+l_c])

 

코드가 지저분하게 짜진 것 같아서 아쉽긴 하지만 직접 풀었다는 것에 만족😫