-
숫자 타자 대회코딩 테스트/Level 3 2022. 11. 30. 13:00반응형
https://school.programmers.co.kr/learn/courses/30/lessons/136797
간단히 완전 탐색. 당연히 시간 제한. 문제는 제대로 이해한 것 같고..
def solution(numbers): def search(left, right, index, total): if len(numbers) == index: return total if left == right: return float('inf') number = int(numbers[index]) left_total = search(number, right, index + 1, total) + weights[left][number] right_total = search(left, number, index + 1, total) + weights[right][number] return min(left_total, right_total) import sys sys.setrecursionlimit(300_000) weights = ((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)) return search(4, 6, 0, 0)
테스트 1 〉 통과 (0.02ms, 10.5MB) 테스트 2 〉 통과 (0.02ms, 10.5MB) 테스트 3 〉 통과 (0.03ms, 10.3MB) 테스트 4 〉 통과 (0.03ms, 10.6MB) 테스트 5 〉 통과 (0.03ms, 10.6MB) 테스트 6 〉 통과 (0.07ms, 10.5MB) 테스트 7 〉 통과 (0.06ms, 10.4MB) 테스트 8 〉 통과 (0.05ms, 10.3MB) 테스트 9 〉 통과 (0.05ms, 10.4MB) 테스트 10 〉 통과 (0.04ms, 10.4MB) 테스트 11 〉 통과 (110.54ms, 10.4MB) 테스트 12 〉 통과 (35.53ms, 10.3MB) 테스트 13 〉 통과 (57.91ms, 10.4MB) 테스트 14 〉 통과 (18.77ms, 10.4MB) 테스트 15 〉 통과 (28.94ms, 10.4MB) 테스트 16 〉 실패 (시간 초과) 테스트 17 〉 실패 (시간 초과) 테스트 18 〉 실패 (시간 초과) 테스트 19 〉 실패 (시간 초과) 테스트 20 〉 실패 (시간 초과)
lru_cache를 이용해 보자.
lru_cache는 함수의 결과를 캐싱해준다. (메모이제이션과 비슷하다.)
간단하게 데코레이터 하나로 재귀함수를 (유사) 동적계획법으로 바꿔준다.
엄청난 파이썬...import sys from functools import lru_cache def solution(numbers): @lru_cache(maxsize=None) def search(left, right, index, total): if len(numbers) == index: return total if left == right: return float('inf') number = int(numbers[index]) left_total = search(number, right, index + 1, total) + weights[left][number] right_total = search(left, number, index + 1, total) + weights[right][number] return min(left_total, right_total) sys.setrecursionlimit(300_000) weights = ((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)) return search(4, 6, 0, 0)
테스트 1 〉 통과 (0.04ms, 10.3MB) 테스트 2 〉 통과 (0.03ms, 10.6MB) 테스트 3 〉 통과 (0.04ms, 10.2MB) 테스트 4 〉 통과 (0.04ms, 10.4MB) 테스트 5 〉 통과 (0.05ms, 10.2MB) 테스트 6 〉 통과 (0.05ms, 10.6MB) 테스트 7 〉 통과 (0.07ms, 10.4MB) 테스트 8 〉 통과 (0.06ms, 10.3MB) 테스트 9 〉 통과 (0.05ms, 10.3MB) 테스트 10 〉 통과 (0.07ms, 10.4MB) 테스트 11 〉 통과 (0.34ms, 10.4MB) 테스트 12 〉 통과 (0.33ms, 10.2MB) 테스트 13 〉 통과 (0.32ms, 10.2MB) 테스트 14 〉 통과 (0.31ms, 10.4MB) 테스트 15 〉 통과 (0.15ms, 10.4MB) 테스트 16 〉 통과 (500.07ms, 109MB) 테스트 17 〉 통과 (753.65ms, 151MB) 테스트 18 〉 통과 (1199.21ms, 230MB) 테스트 19 〉 통과 (1618.83ms, 306MB) 테스트 20 〉 통과 (2571.25ms, 442MB)
너비 우선 탐색(BFS)와 DP로...
def solution(numbers): weights = ((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)) dp = {(4, 6): 0, (6, 4): 0} for number in numbers: number = int(number) new_dp = {} for (idx1, idx2), total in dp.items(): if idx1 == number or idx2 == number: result = min(new_dp.get((idx1, idx2), float('inf')), total + 1) new_dp[(idx1, idx2)] = result new_dp[(idx2, idx1)] = result else: result1 = min(new_dp.get((idx1, number), float('inf')), total + weights[idx2][number]) result2 = min(new_dp.get((idx2, number), float('inf')), total + weights[idx1][number]) new_dp[(idx1, number)] = result1 new_dp[(number, idx1)] = result1 new_dp[(idx2, number)] = result2 new_dp[(number, idx2)] = result2 dp = new_dp return min(dp.values())
테스트 1 〉 통과 (0.02ms, 10.4MB) 테스트 2 〉 통과 (0.03ms, 10.2MB) 테스트 3 〉 통과 (0.02ms, 10.4MB) 테스트 4 〉 통과 (0.03ms, 10.2MB) 테스트 5 〉 통과 (0.05ms, 10.4MB) 테스트 6 〉 통과 (0.06ms, 10.2MB) 테스트 7 〉 통과 (0.05ms, 10.4MB) 테스트 8 〉 통과 (0.06ms, 10.3MB) 테스트 9 〉 통과 (0.05ms, 10.4MB) 테스트 10 〉 통과 (0.05ms, 10.2MB) 테스트 11 〉 통과 (0.44ms, 10.2MB) 테스트 12 〉 통과 (0.25ms, 10.2MB) 테스트 13 〉 통과 (0.24ms, 10.3MB) 테스트 14 〉 통과 (0.44ms, 10.4MB) 테스트 15 〉 통과 (0.27ms, 10.4MB) 테스트 16 〉 통과 (456.63ms, 10.3MB) 테스트 17 〉 통과 (760.18ms, 10.5MB) 테스트 18 〉 통과 (1171.43ms, 10.6MB) 테스트 19 〉 통과 (1519.23ms, 10.5MB) 테스트 20 〉 통과 (2281.02ms, 10.4MB)
반응형