[프로그래머스 Level3] 숫자 타자 대회 - 파이썬(Python)

https://school.programmers.co.kr/learn/courses/30/lessons/136797

프로그래머스

문제 설명

위와 같은 모양으로 배열된 숫자 자판이 있습니다. 숫자 타자 대회는 이 동일한 자판을 사용하여 숫자로만 이루어진 긴 문자열을 누가 가장 빠르게 타이핑하는지 겨루는 대회입니다.

대회에 참가하려는 민희는 두 엄지 손가락을 이용하여 타이핑을 합니다. 민희는 항상 왼손 엄지를 4 위에, 오른손 엄지를 6 위에 두고 타이핑을 시작합니다. 엄지 손가락을 움직여 다음 숫자를 누르는 데에는 일정 시간이 듭니다. 민희는 어떤 두 숫자를 연속으로 입력하는 시간 비용을 몇몇 가중치로 분류하였습니다.

• 이동하지 않고 제자리에서 다시 누르는 것은 가중치가 1입니다.
• 상하좌우로 인접한 숫자로 이동하여 누르는 것은 가중치가 2입니다.
• 대각선으로 인접한 숫자로 이동하여 누르는 것은 가중치가 3입니다.
• 같지 않고 인접하지 않은 숫자를 누를 때는 위 규칙에 따라 가중치 합이 최소가 되는 경로를 따릅니다.

예를 들어 1 위에 있던 손가락을 0으로 이동하여 누르는 것은 2 + 2 + 3 = 7 만큼의 가중치를 갖습니다.
단, 숫자 자판은 버튼의 크기가 작기 때문에 같은 숫자 버튼 위에 동시에 두 엄지 손가락을 올려놓을 수 없습니다. 즉, 어떤 숫자를 눌러야 할 차례에 그 숫자 위에 올려져 있는 손가락이 있다면 반드시 그 손가락으로 눌러야 합니다.

숫자로 이루어진 문자열 numbers가 주어졌을 때 최소한의 시간으로 타이핑을 하는 경우의 가중치 합을 return 하도록 solution 함수를 완성해 주세요. 

 

 

---

이 문제의 핵심은 왼손과 오른손의 이동 가중치가 같을 경우 양쪽 모두 하나씩 탐색해서 푼다면 최악의 경우 2^100,000의 시간 복잡도가 나오는데, 이를 어떻게 해결하느냐이다. 그 해결 방법으로 다이나믹 프로그래밍을 이용했다. 

숫자 자판의 어떠한 위치에서 다음 위치로 갈 때의 최소 이동 가중치를 나중에 바로 꺼내어 확인할 수 있도록 미리 구해두는 것이 좋다. distance 딕셔너리에 두 위치를 키로 두고, 두 위치 간 최소 이동 가중치를 구해 기록했다.

 

 

다음은 다이나믹 프로그래밍이 문제인데, dp에는 (몇 번째 명령으로 주어진 자판인지, 왼손의 키, 오른손의 키)를 넣어 dfs를 진행하며 dp에 들어가 있는 정보라면 이를 재활용함으로써 시간 초과를 줄였다.

 

 

<< 최종 코드 >>

import sys
sys.setrecursionlimit(10**9)

def solution(numbers):
    keyboard = {'1':[0,0], '2':[0,1], '3':[0,2],
                '4':[1,0], '5':[1,1], '6':[1,2],
                '7':[2,0], '8':[2,1], '9':[2,2],
                '*':[3,0], '0':[3,1], '#':[3,2]}
    
    distance = {}
    for start_k, start_pos in keyboard.items():
        for end_k, end_pos in keyboard.items():
            y_gap = abs(start_pos[0] - end_pos[0])
            x_gap = abs(start_pos[1] - end_pos[1])
            common_gap = min(y_gap, x_gap)
            distance[(start_k, end_k)] = max(1, common_gap*3 + (y_gap+x_gap-common_gap*2)*2)

    dp = {}
    def dfs(numbers, i, left, right):
        if i == len(numbers):
            return 0
        if (i, left, right) in dp.keys():
            return dp[(i, left, right)]
        n = numbers[i]
        answer = 10**9
        if right != n:
            answer = min(answer, distance[(left, n)] + dfs(numbers, i+1, n, right))
        if left != n:
            answer = min(answer, distance[(right, n)] + dfs(numbers, i+1, left, n))
        dp[(i, left, right)] = answer
        return answer
    
    return dfs(numbers, 0, '4', '6')