[프로그래머스] 숫자 타자 대회

문제 이해하기 

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

문제 해결 방법 설명하기

1. 경우의 수 계산하기

일단 숫자의 Length가 100,000이기 때문에 완전탐색으 진행한다면 2^100,000이 되니깐 제한시간안에 풀기는 불가능하다.

따라서 다른 접근 법이 필요했다.

 

2. 그리디인가?

다른 접근 법 중 처음 생각난 것은 그리디였다. 왜냐하면 왼손과 오른손 중에 다음 칸에 도달할 수 있는 가장 빠른 경로를 구하면 최적의 답이라고 생각했지만 다음과 같은 경우에는 최적의 답을 찾을 수 없게 된다.

"왼쪽 손이 4번 칸에 위치하고, 오른쪽손이 6번 칸에 위치했을 때 5번 칸으로 이동하려면 어떤 손을 선택해서 이동시켜야 할까?"

 

3. 이분탐색인가?

다음 접근법으로는 이분탐색을 생각해냈다. 이분탐색을 사용하면 시간안에 해결할 수 있지만, 어떻게 하면 최적해를 도출해낼것인가에 대해서 실패했다.

 

4. 완전탐색 + DP

모든 조합을 도출해보고 그 중에 가장 비용이 저렴한 경우가 답이다. 따라서 우리는 왼쪽 손가락을 다음 번호로 옮기는 작업과 오른손 위치를 다음 손가락으로 옮겼을 때 둘 중에 어떤 비용이 더 저렴한지를 알아야 한다. 그것을 알아내는 코드는 다음과 같다.

    left_distance = cost[left_pos][next_pos] + search_number(idx+1, next_pos, right_pos, numbers, cache)
    right_distance = cost[right_pos][next_pos] + search_number(idx+1, left_pos, next_pos, numbers, cache)
    ans = min(left_distance, right_distance)

 

앞에서 언급했듯 단순히 저 방법으로하면 제한시간안에 해결이 불가능하다. 따라서 탐색 횟수를 줄이는 점화식을 설계해야만 한다. 

먼저 점화식 정의는 다음과 같다.

 

"dp[현재 탐색 인덱스][왼손 위치][오른손 위치] = 현재 idx에서 len(numbers)까지 가는 최소한의 비용" 해당

식이 가능한 이유는  앞으로의(다음 숫자 = idx + 1) 경우의 수는 오로지 현재의 손 위치에 따라서 달라지기 떄문이다.

    left_distance = cost[left_pos][next_pos] + search_number(idx+1, next_pos, right_pos, numbers, cache)
    right_distance = cost[right_pos][next_pos] + search_number(idx+1, left_pos, next_pos, numbers, cache)
    ans = min(left_distance, right_distance)		
    cache[(idx, left_pos, right_pos)] = min(left_distance, right_distance)

 

4. 연산 시간은?

메모이제이션을 사용하면 각 (idx, left_pos, right_pos) 튜플당 한 번의 계산만 수행하므로, 각 재귀 호출은 상수 시간에 실행됩니다. 따라서 전체 시간 복잡도는 모든 가능한 (idx, left_pos, right_pos) 튜플의 수에 비례하게 된다. idx는 최대 len(numbers)이고, left_pos와 right_pos는 각각 0부터 9까지의 값을 가질 수 있습니다. 따라서 모든 가능한 (idx, left_pos, right_pos) 튜플의 수는 대략적으로 O(n)입니다. 따라서 메모이제이션을 사용하여 시간 복잡도를 개선하면 각 재귀 호출의 실행 시간을 상수로 유지하고, 전체 시간 복잡도를 O(n)으로 줄일 수 있습니다.

코드

import heapq
import sys
sys.setrecursionlimit(120005)

cost = {}

def search_number(idx, left_pos, right_pos, numbers, cache):
    global cost

    if idx == len(numbers):
        return 0
    
    if (idx, left_pos, right_pos) in cache:
        return cache[(idx, left_pos, right_pos)]

    next_pos = int(numbers[idx])

    if left_pos == next_pos:
        cache[(idx, left_pos, right_pos)] = search_number(idx+1, left_pos, right_pos, numbers, cache) + 1
        return cache[(idx, left_pos, right_pos)]
    
    if right_pos == next_pos:
        cache[(idx, left_pos, right_pos)] = search_number(idx+1, left_pos, right_pos, numbers, cache) + 1
        return cache[(idx, left_pos, right_pos)]
    
    left_distance = cost[left_pos][next_pos] + search_number(idx+1, next_pos, right_pos, numbers, cache)
    right_distance = cost[right_pos][next_pos] + search_number(idx+1, left_pos, next_pos, numbers, cache)

    cache[(idx, left_pos, right_pos)] = min(left_distance, right_distance)    
    
    return cache[(idx, left_pos, right_pos)] 
    
def solution(numbers):
    answer = 0
    global cost
    cache = {}
    
    cost[0] = [1, 7, 6, 7, 5, 4, 5, 3, 2, 3]
    cost[1] = [7, 1, 2, 4, 2, 3, 5, 4, 5, 6]
    cost[2] = [6, 2, 1, 2, 3, 2, 3, 5, 4, 5]
    cost[3] = [7, 4, 2, 1, 5, 3, 2, 6, 5, 4]
    cost[4] = [5, 2, 3, 5, 1, 2, 4, 2, 3, 5]
    cost[5] = [4, 3, 2, 3, 2, 1, 2, 3, 2, 3]
    cost[6] = [5, 5, 3, 2, 4, 2, 1, 5, 3, 2]
    cost[7] = [3, 4, 5, 6, 2, 3, 5, 1, 2, 4]
    cost[8] = [2, 5, 4, 5, 3, 2, 3, 2, 1, 2]
    cost[9] = [3, 6, 5, 4, 5, 3, 2, 4, 2, 1]
    
    answer = search_number(0, 4, 6, numbers, cache)

    return answer


if __name__ == "__main__":
    numbers = "1234"
    result = 10
    
    print(solution(numbers))

코드 리뷰

 

배운점 정리하기

최단 경로를 찾기 위해서 데익스트라를 사용했는데, 해당 알고리즘을 이용하면 시간초과로 문제를 풀 수 없게 된다.따라서 간단한 경우의 수는 미리 계산을 통해서 MAP을 만드는 아이디어를 배웠다. 또한 메모제이션일때 시간복잡도 구하는 것이 힘들었는데 이번 경험으로 다음번에는 더 수월하게 구할 수 있을 것 같다.