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

레벨 2

 

그리디 알고리즘

그리디 알고리즘은 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 알고리즘입니다. 각 단계에서 했던 최선이 선택이 전체적으로 가장 최선의 선택이라고 생각하는 것입니다.

 

조이스틱 문제는 ①커서를 바꾸는 횟수, ②알파벳을 바꾸는 횟수를 합하여 조이스틱을 최소로 조작하는 것입니다. 알파벳을 바꾸는 횟수는 그렇게 어렵지 않습니다. O-ZA-N순으로 알파벳을 정렬하여 아스키 코드 값을 빼줍니다. 문제는 커서를 바꾸는 횟수입니다. 커서를 오른쪽으로 혹은, 왼쪽으로 갈것인지 선택해야 합니다. 또한 한방향으로 쭉 가는 것이 아니라, 오른쪽으로 갔다가 왼쪽으로 갈 수도 있습니다. 예를 들면 'JBAAN'과 같은 경우 B 위치로 커서를 옮긴 후 오른쪽으로 3칸 이동하는 것보다 왼쪽으로 2칸 이동하는 것이 더 이득입니다.

 

따라서 그리디 알고리즘을 적용하여 커서를 이동하도록 작성해봅니다. 현재 커서 위치에서 바꾸어야 할 알파벳이 있는 곳까지 오른쪽과 왼쪽의 인덱스를 셉니다. 둘 중 인덱스가 더 적은 쪽으로 이동을 합니다. 현재의 위치에서 최선의 선택을 하는 것이 그리디 알고리즘이라는 것을 생각해보면 이해가 갈 것입니다. 

 

솔루션

def solution(name):
    answer = 0
    asci=[]
    # name의 각 단어를 아스키 코드로 변환
    for i in name:
        a=ord(i)
        if a>=79:
            asci.append(a-26)
        else:
            asci.append(a)
            
    print(asci)
    first=[ord('A')]*len(name)
    current=0
    
    # 똑같아 질 때까지 반복
    while asci != first:
        left_idx=0
        right_idx=0
        
        # 왼쪽 인덱스 개수 세기
        while asci[current+left_idx] == first[current+left_idx]:
            left_idx-=1
            
        # 오른쪽 인덱스 개수 세기
        while asci[current+right_idx] == first[current+right_idx]:
            right_idx+=1
            
        # 비교 후 현재 인덱스 변경, 커서 개수 세기
        if abs(left_idx)<right_idx:
            current+=left_idx
            answer += abs(left_idx)
        else:
            current+=right_idx
            answer += right_idx
        
        # 변환하기
        answer+= abs(asci[current] - first[current])
        asci[current] = first[current]
        print(left_idx, right_idx, current, answer)
    
    return answer