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

문제 링크

---

프로그래머스

 

 

풀이

---

 

처음에는 현 index에서 가장 가까운 위치를 양쪽에서 찾고 그 위치로 이동하는 방식으로 접근하였으나, 수많은 테스트케이스에서 실패했다. 무조건 가까운 쪽을 선택하는게 최선이 아닌 케이스들이 존재하기 때문이다.

 

예를 들어, ABABAAAAABA를 살펴보자.

위 알고리즘으로 접근하면 최초 [0]에서 [1]위치의 'B'가 제일 가깝기 때문에 여기 먼저 접근하게 된다. 하지만 실제로는 왼쪽으로 먼저 가서 'B'를 바꾼 후에 다시 오른쪽으로 와야 최소 경로가 된다.

 

즉, 매 순간 왼쪽 혹은 오른쪽으로 이동하는 방식으로 접근해야 한다. 어떻게 접근해야 할지 생각이 잘 안나서, 결국 풀이를 봤다. 

moves라는 다음 경로에 합해질 내용을 [-1, 1]로 정해두고 BFS로 접근하면 된다.

 

참고로 idx range가 벗어날 염려가 없다.

• +로 쭉 갈 경우, 0에서 시작되었기 때문에 결국 인덱스 범위를 넘어서기 바로 직전에 모든 arr이 'A'로 변경된다.
• -로 쭉 갈 경우, (배열의 길이)만큼은 -로 가도 문제 없다. 이미 그 바로 직전에 위와 같이 모든 arr이 'A'로 변경될거라 문제 없다.

arr = [1, 2, 3]
print(arr[-3]) // 1 출력
print(arr[-4]) // out of range

 

코드

---

import copy
from collections import deque


def solution(name):
    moves = [-1, 1]
    nameList = list(name)

    # start = (nameList, index, count)
    dq = deque([(nameList, 0, 0)])
    while dq:
        arr, idx, count = dq.pop()
        # 현 위치의 내용을 A로 변경한다.
        count += min(ord(arr[idx]) - 65, 91 - ord(arr[idx]))
        arr[idx] = 'A'

        if arr.count('A') == len(name):
            return count

        for move in moves:
            dq.appendleft((copy.deepcopy(arr), idx + move, count + 1))