프로그래머스 - 조이스틱(파이썬, LV2) / 그리디(Greedy)

https://programmers.co.kr/learn/courses/30/lessons/42860?language=python3

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

먼저 strSol을  'AAAA....' 로 두고 시작점 cursor는 0이다.

이 때 strSol cursor의 위치에 해당하는 name 값으로 변경하고,

현재 가장 가까운 A가 아닌 name의 문자열의 위치로 가서 strSol을 바꾼다.

 

여기서 그리디는 2가지가 된다.
상하의 값 중 현재 가장 최소값으로 변경한다(A에서 Z로내려가는게 빠른지, A에서 B로 올라가는게 빠른지)

좌우의 값 중 'A' 가 아닌 다른 문자열로 바꿔야하는 최단 경로를 찾아 변경한다(왼쪽, 오른쪽)

 

이 두가지의 그리디 룰을 지키면서 값을 이동하면 해결가능하다.

def solution(name):
    answer = 0
    strSol = ['A'] * len(name)
    same = [False] * len(name)   # 같아졌는지
    cursor = 0
    
    # 다른 곳 파싱
    for a in range(len(name)):
        if strSol[a] != name[a]:
            same[a] = False # 다름
        else:
            same[a] = True # 같음
    
    while(True):
        # 같을 때 까지 진행
        if((False in same) is False):
            break
        
        # 가장 가까운 곳 찾아서
        diff = 0
        while(True):
            if(same[cursor] == False):
                break
                
            # 안될 경우 diff 증가
            diff += 1

            # 오른쪽 이동
            if ( same[(cursor + diff) % len(name)] == False) :
                cursor =  (cursor + diff) % len(name)
            
            # 왼쪽 이동
            elif ( same[(cursor - diff) % len(name)] == False) :
                cursor =  (cursor - diff) % len(name)
            
        
        # 해당 변경
        answer += diff
        name_char = ord(name[cursor]) - ord('A') # A로부터 올라가기
        z_char = ord('Z') - ord('A') +1 # Z로부터 내려가기
        answer += min(name_char, (z_char - name_char))
        strSol[cursor] = name[cursor]
        same[cursor] = True
                
    
    return answer