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

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

• 항상 왼손 엄지를 4 위에, 오른손 엄지를 6 위에 두고 타이핑을 시작합니다.

• 이동하지 않고 제자리에서 다시 누르는 것은 가중치가 1입니다.

• 상하좌우로 인접한 숫자로 이동하여 누르는 것은 가중치가 2입니다.

• 대각선으로 인접한 숫자로 이동하여 누르는 것은 가중치가 3입니다.

• 같지 않고 인접하지 않은 숫자를 누를 때는 위 규칙에 따라 가중치 합이 최소가 되는 경로를 따릅니다.

• 어떤 숫자를 눌러야 할 차례에 그 숫자 위에 올려져 있는 손가락이 있다면 반드시 그 손가락으로 눌러야 합니다.

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

제한 사항

• 1 ≤ numbers의 길이 ≤ 100,000

이 문제를 풀이할 때, 가장 먼저 살펴야 하는 것은 numbers의 길이 이다. 100,000의 길이를 가지기 때문에 숫자 하나에 대해 left or right를 결정하게 될 경우(완전 탐색) O(2^n)의 탐색 시간을 소요하게 될 것이다...

이렇게 되면 어떤 곳에도 사용하기 힘든 고비용의 알고리즘이 된다. ㅠㅠ

그래서 이 시간을 어떻게 해야 줄일 수 있을까에 대해 하루 넘게 생각을 해보았지만 뾰족한 방법이 필자의 머리를 스치는 일은 없었다. 그래서 여러 포스팅을 참고한 결과 동적계획법을 이용한 방법이 최적일 것으로 생각되었다.

풀이의 주요 컨셉은 다음과 같다.

• 첫 번째로 탐색 숫자에 대한 왼쪽, 오른쪽 손가락 위치와 탐색 가중치를 저장해야 한다는 것이다. (memoization)

이때 문제에서는 경로를 요구하지 않으므로 현재 손가락 위치만 기록하면 된다. 예를 들어 (left_pos, right_pos, weight)와 같은 tuple 혹은 list 혹은 object와 같은 자료 구조를 사용한다.

• 두 번째는 기록한 손가락 위치와 가중치를 다음 숫자 탐색으로 전달하고 숫자를 탐색할 때, (left_pos, right_pos, weight + now_weight)와 같은 형식으로 갱신해준다.

두 번째까지의 컨셉을 지켜 순회하게 되면 완전 탐색을 하게 되는데 우리는 탐색 수를 더욱 줄여야만 한다. 따라서

• 세 번째로 현재 기록하고 있는 손가락 위치들 중에 중복되는 경우를 찾아서 작은 값을 선택하게 해야 한다.

예를 들어 (left_pos = 4, right_pos = 6)인 상태에서 5로 이동해야 하는 경우, 왼쪽으로 이동하든 오른쪽으로 이동하든 어느 쪽이 맞는지 현재 상태에서는 결정할 수 없다.

따라서 이런 경우에는 다음 단계로 두 가지 경우 모두를 전달하고 이후에 1로 이동해야 한다면 (5,6)과 (4,5) 중 (4,5)를 선택하고 (1,5)로 이동하는 경우를 선택해야 한다.

이처럼 모든 예외를 통제하기 위해 현재 같은 위치에 대해서만 더 작은 가중치를 기록하도록 하는 것이다.(여기에는 설명하지 못한 예외들이 더 있는데 직접 생각해보셨으면 좋겠습니다... 설명하기 어려워서)

생각보다 10개 위치에 대해 구별되는 2개 노드의 위치에 대한 경우의 수는 많지 않다. Permuation(10, 2)이기 때문에 90가지의 경우가 나온다. 이는 2^n으로 늘어나는 경우의 수보다 훨씬 적고 90에서 더는 늘어나지 않으므로 상수 시간으로도 볼 수 있다.

풀이에는 dictionary 자료구조를 사용해서 풀이를 했는데 이론 상 list를 사용해도 상수 시간일 것으로 보인다.

아무튼 all_dict의 길이가 90을 넘어가지 않으므로 for문으로 순회하더라도 상수 시간이다. dictionary는 해시 테이블이므로 개별 요소에 대한 검색 시간이 O(1)이다. 따라서 전체 문제 풀이의 시간 복잡도는 O(n)이라고 할 수 있다.

실제로 numbers의 길이가 100000일 때 걸리는 시간은 약 1초 정도이고 1000000일 때는 10초, 10000000일 때는 100초 정도로 정확히 O(n)으로 증가하는 것을 확인했다!

costs =     [[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]]

def solution(numbers):
    now_weight = 0
    left_pos = 4
    right_pos = 6
    all_dict = {}
    finger_pos = (left_pos, right_pos)
    all_dict[finger_pos] = now_weight
    
    for str_num in numbers:
        num = int(str_num)
        curr_dict = {}
        for finger_pos, weight in all_dict.items():
            left_pos, right_pos = finger_pos
            if right_pos == num:
                if not (left_pos, num) in curr_dict.keys() or curr_dict[(left_pos, num)] > weight + 1:
                    curr_dict[(left_pos, num)] = weight + 1
            elif left_pos == num:
                if not (num, right_pos) in curr_dict.keys() or curr_dict[(num, right_pos)] > weight + 1:
                    curr_dict[(num, right_pos)] = weight + 1
            else:
                if not (left_pos, num) in curr_dict.keys() or curr_dict[(left_pos, num)] > weight + costs[right_pos][num]:
                    curr_dict[(left_pos, num)] = weight + costs[right_pos][num]
                if not (num, right_pos) in curr_dict.keys() or curr_dict[(num, right_pos)] > weight + costs[left_pos][num]:
                    curr_dict[(num, right_pos)] = weight + costs[left_pos][num]
        all_dict = curr_dict

    return min(list(all_dict.values()))