[programmers] 조이스틱

Link

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

---

Code

def solution(name):
    answer = 0
    min_move = len(name) - 1
    for i, char in enumerate(name):
        answer += min(ord(char) - ord('A'), ord('Z') - ord(char) + 1)
        nxt = i + 1
        while (nxt < len(name) and name[nxt] == 'A'):
            nxt += 1
        min_move = min([min_move, 2 * i + len(name) - nxt, i + 2 * (len(name) - nxt)])
    answer += min_move
    return answer

---

Solution

이미 옛날에 풀었던 문제기도 하고 문제 항목이 그리디여서 예전처럼 그리디로 해결하면 풀리겠거니 했지만 절대 풀리지 않았다. 그래서 대체 뭐가 부족한지 찾아보니 테스트 케이스가 추가되면서 그리디로 푸는 방식이 아니어서 다른 분의 코드를 가져와보았다.
각 인덱스마다 알파벳 바꾸는데 최소값을 찾아 answer에 더해준다. 여기서 중요한게 위치를 찾는건데 그리디로 풀면 안되고 가장 긴 A의 길이를 찾아야한다. 현재 인덱스 옆에 있는 A의 위치nxt를 찾은후 min_move는 모든 문자열 탐색, 현재 위치에서 찾은 긴 A의 왼쪽까지 간후(+) 왼쪽으로 탐색(-)하는 경우, 현재 위치에서 찾은 긴 A의 오른쪽까지 간후(-) 오른쪽으로 탐색(+) 인경우를 모두 비교한후 나온 최소 min_move를 answer에 더해주고 리턴