[ 프로그래머스 / LV3 / 파이썬 Python ] 숫자 타자 대회

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

프로그래머스

 

코드 - DP (성공)

---

from heapq import heappop, heappush
def solution(numbers):
    
    dist = [
    [1, 7, 6, 7, 5, 4, 5, 3, 2, 3], 
    [7, 1, 2, 4, 2, 3, 5, 4, 5, 6], 
    [6, 2, 1, 2, 3, 2, 3, 5, 4, 5], 
    [7, 4, 2, 1, 5, 3, 2, 6, 5, 4], 
    [5, 2, 3, 5, 1, 2, 4, 2, 3, 5], 
    [4, 3, 2, 3, 2, 1, 2, 3, 2, 3], 
    [5, 5, 3, 2, 4, 2, 1, 5, 3, 2], 
    [3, 4, 5, 6, 2, 3, 5, 1, 2, 4], 
    [2, 5, 4, 5, 3, 2, 3, 2, 1, 2], 
    [3, 6, 5, 4, 5, 3, 2, 4, 2, 1], 
    ]
    
    L = len(numbers:=list(map(int,list(numbers))))
    dp = [[[1e9]*12 for _ in range(12)] for _ in range(L+1)] # dp[인덱스][왼손][오른손]
    queue = [(0,4,6)]
    dp[0][4][6] = 0
    hands = []
    while queue:
        idx,left,right = heappop(queue)
        
        if idx > L-1: 
            hands.append((left,right))
            continue
            
        number = numbers[idx]
        rightChange = dp[idx][left][right] + dist[right][number]
        leftChange = dp[idx][left][right] + dist[left][number]
        
        if right != number and dp[idx+1][number][right] > leftChange:
            dp[idx+1][number][right] = leftChange
            heappush(queue,(idx+1,number,right))
        
        if left != number and dp[idx+1][left][number] > rightChange:
            dp[idx+1][left][number] = rightChange
            heappush(queue,(idx+1,left,number))
    
    return min([dp[L][x][y] for x,y in hands])

 

풀이

---

맨 처음에는 dist로 만든 배열 자체를 "플로이드 워샬" 알고리즘을 사용해서 생성했다. 하지만 시간이 너무 오래 걸렸고 문제에서 변수가 아닌 작은 상수로 주어지는 범위에 대해서는 쌩코딩으로 만들어야 한다는 것을 깨닫게 되었다.

 

dist라는 배열은 한 번호에서 다른 번호로 넘어갈 때 발생하는 비용이다. dist[4][5]는 4번에 있던 손가락이 5번을 누르는데에 발생하는 비용인 것이다. 

 

이 문제의 조건에는 numbers의 길이가 10만까지 올라간다고 나와있다. 맨 아래의 코드처럼 완전탐색을 시도하게되면 (왼손으로 누르기, 오른손으로 누르기) 이 두가지 경우를 10만번 반복하게 되어 O(2**10만)으로 시간초과가 발생하게 된다. 따라서 DP를 사용해야 겠다고 생각했다. DP를 만들려 했는데 고려해야 할 대상이 (누를 숫자, 왼손의 위치, 오른손의 위치)로 세개이기 때문에 드물지 않게 삼차원 배열을 만들어야 했다. 

 

문제의 조건에 두 손가락이 한 위치에 있으면 안된다고 나와있기 때문에 어떤 손을 옮길 때에는 반대손이 이미 해당 숫자에 위치하지 않는다는 조건을 넣었고 dp[누를 숫자의 인덱스][왼손][오른손]의 값을 작은 방향으로 갱신해주었다.

 

인덱스가 마지막까지 다다르고 그 이상으로 넘어가면 왼손가락과 오른손가락 중 하나는 마지막 숫자를 누르고 있는 상태이다. 그 상태를 모두 배열로 저장하여 dp에서 최솟값을 리턴해주었다.

 

 

 

---

코드 - 완전탐색 (실패)

---

from collections import deque
def solution(numbers):
    dist = [
    [1, 7, 6, 7, 5, 4, 5, 3, 2, 3], 
    [7, 1, 2, 4, 2, 3, 5, 4, 5, 6], 
    [6, 2, 1, 2, 3, 2, 3, 5, 4, 5], 
    [7, 4, 2, 1, 5, 3, 2, 6, 5, 4], 
    [5, 2, 3, 5, 1, 2, 4, 2, 3, 5], 
    [4, 3, 2, 3, 2, 1, 2, 3, 2, 3], 
    [5, 5, 3, 2, 4, 2, 1, 5, 3, 2], 
    [3, 4, 5, 6, 2, 3, 5, 1, 2, 4], 
    [2, 5, 4, 5, 3, 2, 3, 2, 1, 2], 
    [3, 6, 5, 4, 5, 3, 2, 4, 2, 1], 
    ]
    
    q = deque([(4,6,0,0)])
    answer = 1e9
    l = len(numbers)
    while q:
        left,right,idx,total = q.popleft()
        if idx >= l:
            answer = min(answer,total)
            continue
        number = int(numbers[idx])
        if (lc:=dist[left][number]) > (rc:=dist[right][number]):
            q.append((left,number,idx+1,total+rc))
        elif lc < rc:
            q.append((number,right,idx+1,total+lc))
        else:
            q.append((left,number,idx+1,total+rc))
            q.append((number,right,idx+1,total+lc))
            
    return answer