[TIL_Carrotww] 56 - 22/11/21

📝Carrotww의 코딩 기록장

🧲 python algorithm

🔍 programmers 숫자 타자 대회 level3
이 문제도 푼 사람이 100명 미만인 따끈 따근한 문제이다
처음에 어떻게 접근해야할지 감이 안잡혔지만 일단! 풀어본 문제이다.

• 첫 풀이

import sys
sys.setrecursionlimit(10**9)

def solution(numbers):
    left, right = 4, 6
    depth = [
        	[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
    result = []

    def dfs(number_po, total_val, left, right):
        # number_po 의 위치가 numbers 의 끝까지 갔으면 종료
        if number_po > len(numbers) - 1:
            result.append(total_val)
            return
        change_num = int(numbers[number_po])
        # 바궈야할 번호
        left_val = depth[left][change_num]
        right_val = depth[right][change_num]
        # 왼쪽과 오른쪽의 다음 가중치
        if left_val < right_val:
            total_val += left_val
            dfs(number_po + 1, total_val, change_num, right)
        elif right_val < left_val:
            total_val += right_val
            dfs(number_po + 1, total_val, left, change_num)
        elif left_val == right_val:
            total_val += left_val
            dfs(number_po + 1, total_val, change_num, right)
            dfs(number_po + 1, total_val, left, change_num)

중간에 실패가 뜨고 마지막 5개가 시간 초과가 난다.
시간 초과가 났다는 것은... 어지간하면 접근 방식이 이게 아니라는건데... 일단 문제를 다시 읽고 풀어보았다.
그 때 손 위에 있는 번호는 무조건 눌러야 한다 해서 그 대로 코드에 넣어봤다.
첫 번째 코드도 자기 손 위에 있는 번호를 누를텐데 라는 의문을 가지며...

• 두 번째 풀이

import sys
sys.setrecursionlimit(10**9)

def solution(numbers):
    left, right = 4, 6
    depth = [
        	[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
    result = []

    def dfs(number_po, total_val, left, right):
        # number_po 의 위치가 numbers 의 끝까지 갔으면 종료
        if number_po > len(numbers) - 1:
            result.append(total_val)
            return

        change_num = int(numbers[number_po])
        # 움직여야할 다음 번호
        left_val = depth[left][change_num]
        right_val = depth[right][change_num]

        # 왼쪽과 오른쪽의 다음 가중치
        if left_val == 1:
            dfs(number_po + 1, total_val + left_val, change_num, right)
        elif right_val == 1:
            dfs(number_po + 1, total_val + right_val, left, change_num)
        # 가중치가 1일때는 해당 번호 위에 손가락이 있다는 것이니까 그대로 눌러야함
        else:
            dfs(number_po + 1, total_val + left_val, change_num, right)
            dfs(number_po + 1, total_val + right_val, left, change_num)
       	return

    # dfs -> 매개변수 : 현재 numbers의 위치, 지금까지의 가중치, left, right 손가락 위치!

역시 문제에 답이 있었다.
하지만 시간 초과는 역시... dfs 로 풀기는 했지만 다른 풀이로는 왼손 오른쪽을 나누어서 dp로 기록하며 나아가면 시간을 줄일 수 있을 것 같다.
내일 다시 풀어봐야겠다.
오늘 끝!