[프로그래머스] 조이스틱

---

문제설명

https://programmers.co.kr/learn/courses/30/lessons/42860#

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

사고과정

• 그리디 문제인데, 상/하 방향, 좌/우 방향 두 개의 기준으로 각각 최소값을 갱신해야 했었다. 개인적으로 그리디 문제가 좀 체감이 많이 어렵다.. 마치 숨겨진 규칙을 찾는 느낌... 애써 풀어보려고 했지만 실패했다..
• 구글링을 해서 다른 분의 좋은 풀이를 참고했다. 나는 주어진 문자열에서 모든 문자열을 A로 만드는 관점으로 생각했는데, 이를 반대로 생각하면 문제 풀이가 원활해진다. 
• 그래서 처음에는 각 위치에서 상/하 방향 중 가장 짧은 거리를 원소로 하는 문자열로 변환을 취한다. 그리고 변환시킨 값을 0으로 바꾸어주어서 해당 원소가 'A'라는 것을 의미하도록 일종의 방문처리를 해준다.
• 그리고 난 후 각각 좌, 우 방향으로  무한 loop를 돌면서 왼쪽/오른쪽 거리를 계산한다. 그리고 이 중 짧은 거리를 적용해 계산해준다..
• 어렵다리...

풀이(스스로 못 푼 풀이)

def solution(name):
    # 상,하 중 우선 이동 거리 갱신
    change = [min(ord(n)-ord('A'), ord('Z')-ord(n)+1) for n in name]
    answer = 0
    idx = 0
    
    while True:
        # 상,하 중 최소 거리 갱신 및 방문 처리
        answer += change[idx]
        change[idx] = 0
        # 만약 모든 문자열 A라고 한다면 return
        if sum(change) == 0:
            return answer
        
        # 좌,우 중 최소 거리 갱신
        left, right = 1, 1
        while change[idx - left] == 0: # A라면! 더 왼쪽으로 이동
            left += 1
        while change[idx + right] == 0: # A라면! 더 오른쪽으로 이동
            right += 1
        
        answer += left if left < right else right
        idx += -left if left < right else right  # 왼쪽으로 이동 시 음수붙여주기!