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

문제

• 숫자로만 이루어진 긴 문자열을 누가 가장 빠르게 타이핑하는지 겨루는 대회
• 항상 왼손 엄지를 4 위에, 오른손 엄지를 6 위에 두고 타이핑을 시작
• 엄지 손가락을 움직여 다음 숫자를 누르는 데에는 일정 시간이 든다.
  • 이동하지 않고 제자리에서 다시 누르는 것은 가중치가 1입니다.
  • 상하좌우로 인접한 숫자로 이동하여 누르는 것은 가중치가 2입니다.
  • 대각선으로 인접한 숫자로 이동하여 누르는 것은 가중치가 3입니다.
  • 같지 않고 인접하지 않은 숫자를 누를 때는 위 규칙에 따라 가중치 합이 최소가 되는 경로를 따릅니다.
• 숫자 자판은 버튼의 크기가 작기 때문에 같은 숫자 버튼 위에 동시에 두 엄지 손가락을 올려놓을 수 없습니다.
• 1 <= 숫자 길이 <= 100,000

 

풀이 1

• 시간 복잡도
  • 모든 경우의 수 : 각 숫자를 왼쪽/오른쪽 손가락으로 누르는 경우로 $O(2^N)$ 이 됨
  • 경우의 수를 줄여야한다!
• 최소 비용 구하는 부분을 bfs로 생각했는데, 시간 초과 난다.
  • 숫자가 10개 밖에 없고, 경우의 수가 모두 정해져 있으므로 각 숫자별 최소비용 정해두기
  • cost[a][b] : a 숫자에서 b숫자 누를 때 비용 
• 경우의 수 확인하는 것을 dfs 로 생각했는데, 이렇게 하면 시간 초과 난다.
  • 우선 
  • 1~15까지 통과, 16번부터 시간 초과

 

import sys
sys.setrecursionlimit(10**6)

# cost[i][j] : i번째 숫자에서 j번째 숫자 누를 때 비용
cost = [
    [1, 7, 6, 7, 5, 4, 5, 3, 2, 3], # 0
    [7, 1, 2, 4, 2, 3, 5, 4, 5, 6], # 1
    [6, 2, 1, 2, 3, 2, 3, 5, 4, 5], # 2
    [7, 4, 2, 1, 5, 3, 2, 6, 5, 4], # 3
    [5, 2, 3, 5, 1, 2, 4, 2, 3, 5], # 4
    [4, 3, 2, 3, 2, 1, 2, 3, 2, 3], # 5
    [5, 5, 3, 2, 4, 2, 1, 5, 3, 2], # 6
    [3, 4, 5, 6, 2, 3, 5, 1, 2, 4], # 7
    [2, 5, 4, 5, 3, 2, 3, 2, 1, 2], # 8
    [3, 6, 5, 4, 5, 3, 2, 4, 2, 1], # 9
]

def dfs(numbers, left, right):
    if not numbers :
        return 0
    
    answer = sys.maxsize
    if left == numbers[0] :
        answer = min(answer, dfs(numbers[1:], numbers[0], right) + 1)
    elif right == numbers[0] :
        answer = min(answer, dfs(numbers[1:], left, numbers[0]) + 1)
    else :
        answer = min(answer, dfs(numbers[1:], numbers[0], right) + cost[left][numbers[0]])
        answer = min(answer, dfs(numbers[1:], left, numbers[0]) + cost[right][numbers[0]])
    
    return answer

def solution(numbers):
    numbers = list(map(int, numbers))
    
    return dfs(numbers, 4, 6)

 

 

풀이 2

• dfs 로 안되는 것을 보니 확인하지 않아도 되는 부분을 중간에 컷트해줘야 한다.
• memoization을 활용해 n번째 숫자 확인 시 손가락 위치별 최소 비용 기록하기

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

# cost[i][j] : i번째 숫자에서 j번째 숫자 누를 때 비용
cost = [
    [1, 7, 6, 7, 5, 4, 5, 3, 2, 3], # 0
    [7, 1, 2, 4, 2, 3, 5, 4, 5, 6], # 1
    [6, 2, 1, 2, 3, 2, 3, 5, 4, 5], # 2
    [7, 4, 2, 1, 5, 3, 2, 6, 5, 4], # 3
    [5, 2, 3, 5, 1, 2, 4, 2, 3, 5], # 4
    [4, 3, 2, 3, 2, 1, 2, 3, 2, 3], # 5
    [5, 5, 3, 2, 4, 2, 1, 5, 3, 2], # 6
    [3, 4, 5, 6, 2, 3, 5, 1, 2, 4], # 7
    [2, 5, 4, 5, 3, 2, 3, 2, 1, 2], # 8
    [3, 6, 5, 4, 5, 3, 2, 4, 2, 1], # 9
]

# cache[i][(left,right)] : i번째 숫자에서 (left, right) 위치의 최소 비용
cache = defaultdict(dict)

def dfs(i, numbers, left, right):
    if i == len(numbers) :
        return 0
    
    # memoization 활용
    if (left, right) in cache[i]:
        return cache[i][(left,right)]
    
    answer = sys.maxsize
    num = numbers[i]
    if left == num :
        answer = min(answer, dfs(i+1, numbers, num, right) + 1)
    elif right == num :
        answer = min(answer, dfs(i+1, numbers, left, num) + 1)
    else :
        answer = min(answer, dfs(i+1, numbers, num, right) + cost[left][num])
        answer = min(answer, dfs(i+1, numbers, left, num) + cost[right][num])
    cache[i][(left,right)] = answer
    return answer

def solution(numbers):
    numbers = list(map(int, numbers))
    cache[(4,6)] = 0
    
    return dfs(0, numbers, 4, 6)

 

풀이 3

• 모든 숫자 길이별로 저장하는 건 공간복잡도 면에서 비효율적이다.
  • 반복문으로 바꾸고 해당 숫자에서 확인해야 할 리스트만 관리하기!
• 각 숫자 별로 한 번씩 최소 경로 확인하기 $O(N*M)$
  • M : 한 숫자의 최소 경로 확인하는 비용
  • N = 100000 이므로 M < 400 이면 된다.

# cost[i][j] : i번째 숫자에서 j번째 숫자 누를 때 비용
cost = [
    [1, 7, 6, 7, 5, 4, 5, 3, 2, 3], # 0
    [7, 1, 2, 4, 2, 3, 5, 4, 5, 6], # 1
    [6, 2, 1, 2, 3, 2, 3, 5, 4, 5], # 2
    [7, 4, 2, 1, 5, 3, 2, 6, 5, 4], # 3
    [5, 2, 3, 5, 1, 2, 4, 2, 3, 5], # 4
    [4, 3, 2, 3, 2, 1, 2, 3, 2, 3], # 5
    [5, 5, 3, 2, 4, 2, 1, 5, 3, 2], # 6
    [3, 4, 5, 6, 2, 3, 5, 1, 2, 4], # 7
    [2, 5, 4, 5, 3, 2, 3, 2, 1, 2], # 8
    [3, 6, 5, 4, 5, 3, 2, 4, 2, 1], # 9
]

def solution(numbers):
    numbers = list(map(int, numbers))
    q = {(4, 6): 0}     # 확인해야 할 리스트

    for num in numbers: 
        now_q = {}      # 다음에 확인 할 리스트
        for finger, w in q.items():
            left, right = finger
            
            # 왼쪽 위치와 동일한 경우
            if left == num :
                # 리스트에 추가되지 않았거나 최소 비용이 아닌 경우
                if not (num, right) in now_q or now_q[(num, right)] > w + 1:
                    now_q[(num, right)] = w + 1
            # 오른쪽 위치와 동일한 경우
            elif right == num : 
                # 리스트에 추가되지 않았거나 최소 비용이 아닌 경우
                if not (left, num) in now_q or now_q[(left, num)] > w + 1:
                    now_q[(left, num)] = w + 1
            else:
                if not (num, right) in now_q or now_q[(num, right)] > w + cost[left][num] :
                    now_q[(num, right)] = w + cost[left][num]
                if not (left, num) in now_q or now_q[(left, num)] > w + cost[right][num] :
                    now_q[(left, num)] = w + cost[right][num]
    
        q = now_q
    
    return min(list(q.values()))

 

References

• 프로그래머스 Lv3 숫자 타자 대회