-
2017 팁스타운: 단어 퍼즐코딩 테스트/Level 4 2022. 12. 8. 00:44반응형
https://school.programmers.co.kr/learn/courses/30/lessons/12983
def solution(pieces, word): pieces = set(pieces) dp = [float('inf') for _ in range(len(word) + 1)] dp[0] = 0 for index, _ in enumerate(word): if dp[index] == float('inf'): continue for len_piece in range(1, 6): if index + len_piece <= len(word) and word[index:][:len_piece] in pieces: dp[index + len_piece] = min(dp[index + len_piece], dp[index] + 1) return dp[-1] if dp[-1] != float('inf') else -1
문제를 대충 읽었다.
piece의 길이가 1~5라는 조건을 읽지 못했고,
그래서 모든 piece의 길이를 확인했었는데,
이것이 실패의 원인이었다.이 조건을 알았다면 해시(셋)를 이용할 생각을 했을 수도 있는데...
모르는 상황에서는 생각조차 하지 못했다.단순히 DP만 쓰면 통과할 줄 았았던 게 패착...
레벨 4는 이 정도 디테일까지 신경 써야 하는구나..정확성 테스트 테스트 1 〉 통과 (0.03ms, 10.3MB) 테스트 2 〉 통과 (0.06ms, 10.3MB) 테스트 3 〉 통과 (0.01ms, 10.3MB) 테스트 4 〉 통과 (0.11ms, 10.2MB) 테스트 5 〉 통과 (0.18ms, 10.2MB) 테스트 6 〉 통과 (0.02ms, 10.3MB) 테스트 7 〉 통과 (0.38ms, 10.3MB) 테스트 8 〉 통과 (2.29ms, 10.2MB) 테스트 9 〉 통과 (4.09ms, 10.1MB) 테스트 10 〉 통과 (4.12ms, 10.2MB) 테스트 11 〉 통과 (4.10ms, 10.3MB) 테스트 12 〉 통과 (0.02ms, 10.2MB) 테스트 13 〉 통과 (0.03ms, 10.3MB) 테스트 14 〉 통과 (0.03ms, 10.2MB) 테스트 15 〉 통과 (0.03ms, 10.1MB) 테스트 16 〉 통과 (0.02ms, 10.3MB) 테스트 17 〉 통과 (0.02ms, 10.3MB) 테스트 18 〉 통과 (0.03ms, 10.1MB) 테스트 19 〉 통과 (0.04ms, 10.2MB) 효율성 테스트 테스트 1 〉 통과 (70.61ms, 10.8MB) 테스트 2 〉 통과 (59.92ms, 10.7MB) 테스트 3 〉 통과 (70.94ms, 10.7MB) 테스트 4 〉 통과 (62.78ms, 10.7MB) 테스트 5 〉 통과 (54.02ms, 10.8MB)
아래는 실패
----------------------------------------------------------재귀와 DFS로 코딩해 보았다.
통과는 못하겠지만 코딩이 간결(?)할 것 같아서.
하지만 그것도 아니었다...def solution(pieces, word): def search(index, counter): if index >= len(word): return counter return min(results) if (results := [search(index + len(each), counter + 1) for each in pieces if word[index:index + len(each)] == each]) else float('inf') return -1 if (result := search(0, 0)) == float('inf') else result
예상했던 런타임 에러와 시간 초과..
테스트 1 〉 통과 (0.03ms, 10.2MB) 테스트 2 〉 통과 (0.29ms, 10.1MB) 테스트 3 〉 통과 (0.01ms, 10.1MB) 테스트 4 〉 통과 (1.22ms, 10.2MB) 테스트 5 〉 통과 (216.47ms, 10MB) 테스트 6 〉 통과 (0.01ms, 10.2MB) 테스트 7 〉 실패 (시간 초과) 테스트 8 〉 실패 (런타임 에러) 테스트 9 〉 실패 (런타임 에러) 테스트 10 〉 실패 (런타임 에러) 테스트 11 〉 실패 (런타임 에러) 테스트 12 〉 통과 (0.03ms, 10.2MB) 테스트 13 〉 통과 (0.56ms, 10.1MB) 테스트 14 〉 통과 (0.90ms, 10.1MB) 테스트 15 〉 통과 (0.24ms, 9.99MB) 테스트 16 〉 통과 (0.01ms, 10.2MB) 테스트 17 〉 통과 (0.01ms, 10.3MB) 테스트 18 〉 통과 (0.05ms, 10.2MB) 테스트 19 〉 통과 (0.03ms, 10.3MB)
BFS로 코딩.. 망함
def solution(pieces, word): from collections import deque queue = deque([(0, 0)]) # index, counter while queue: index, counter = queue.popleft() if index == len(word): return counter for piece in pieces: if word[index:][:len(piece)] == piece: queue.append((index + len(piece), counter + 1)) return -1
테스트 1 〉 통과 (0.03ms, 10.1MB) 테스트 2 〉 통과 (0.31ms, 10.3MB) 테스트 3 〉 통과 (0.01ms, 10.2MB) 테스트 4 〉 통과 (1.03ms, 10.4MB) 테스트 5 〉 통과 (86.58ms, 11.8MB) 테스트 6 〉 통과 (0.01ms, 10.1MB) 테스트 7 〉 실패 (시간 초과) 테스트 8 〉 실패 (시간 초과) 테스트 9 〉 실패 (시간 초과) 테스트 10 〉 실패 (시간 초과) 테스트 11 〉 실패 (시간 초과) 테스트 12 〉 통과 (0.02ms, 10.2MB) 테스트 13 〉 통과 (0.07ms, 10.3MB) 테스트 14 〉 통과 (0.08ms, 10.1MB) 테스트 15 〉 통과 (0.09ms, 10.3MB) 테스트 16 〉 통과 (0.01ms, 10MB) 테스트 17 〉 통과 (0.02ms, 10.2MB) 테스트 18 〉 통과 (0.03ms, 10.1MB) 테스트 19 〉 통과 (0.02ms, 10.2MB)
그럼 BFS와 방문 체크로... 망함
def solution(pieces, word): from collections import deque queue = deque([(0, 0)]) # index, counter visited = set() while queue: index, counter = queue.popleft() if index in visited: continue visited.add(index) if index == len(word): return counter for piece in pieces: if word[index:][:len(piece)] == piece: queue.append((index + len(piece), counter + 1)) return -1
정확성 테스트 테스트 1 〉 통과 (0.02ms, 10.2MB) 테스트 2 〉 통과 (0.03ms, 10.3MB) 테스트 3 〉 통과 (0.01ms, 10.2MB) 테스트 4 〉 통과 (0.04ms, 10.3MB) 테스트 5 〉 통과 (0.07ms, 10.3MB) 테스트 6 〉 통과 (0.01ms, 10.3MB) 테스트 7 〉 통과 (0.26ms, 10.3MB) 테스트 8 〉 통과 (3.31ms, 10.4MB) 테스트 9 〉 통과 (3.43ms, 10.3MB) 테스트 10 〉 통과 (3.92ms, 10.2MB) 테스트 11 〉 통과 (4.61ms, 10.1MB) 테스트 12 〉 통과 (0.02ms, 10.3MB) 테스트 13 〉 통과 (0.03ms, 10.4MB) 테스트 14 〉 통과 (0.03ms, 10.2MB) 테스트 15 〉 통과 (0.02ms, 10.2MB) 테스트 16 〉 통과 (0.01ms, 10.3MB) 테스트 17 〉 통과 (0.01ms, 10.2MB) 테스트 18 〉 통과 (0.02ms, 10.2MB) 테스트 19 〉 통과 (0.02ms, 10.2MB) 효율성 테스트 테스트 1 〉 실패 (시간 초과) 테스트 2 〉 실패 (시간 초과) 테스트 3 〉 실패 (시간 초과) 테스트 4 〉 실패 (시간 초과) 테스트 5 〉 실패 (시간 초과)
문제의 조건을 확인한 뒤 풀어봄...
def solution(pieces, word): from collections import deque pieces = set(pieces) queue = deque([(0, 0)]) # index, counter visited = set() while queue: index, counter = queue.popleft() if index in visited: continue visited.add(index) if index == len(word): return counter for i in range(1, 6): if word[index:][:i] in pieces: queue.append((index + i, counter + 1)) return -1
정확성 테스트 테스트 1 〉 통과 (0.02ms, 10.2MB) 테스트 2 〉 통과 (0.05ms, 10MB) 테스트 3 〉 통과 (0.01ms, 10.2MB) 테스트 4 〉 통과 (0.04ms, 10.2MB) 테스트 5 〉 통과 (0.08ms, 10.3MB) 테스트 6 〉 통과 (0.01ms, 9.99MB) 테스트 7 〉 통과 (0.16ms, 10.2MB) 테스트 8 〉 통과 (1.51ms, 10.4MB) 테스트 9 〉 통과 (1.65ms, 10.2MB) 테스트 10 〉 통과 (2.19ms, 10.2MB) 테스트 11 〉 통과 (1.62ms, 10.3MB) 테스트 12 〉 통과 (0.02ms, 10.2MB) 테스트 13 〉 통과 (0.03ms, 10.3MB) 테스트 14 〉 통과 (0.03ms, 10.2MB) 테스트 15 〉 통과 (0.02ms, 10.2MB) 테스트 16 〉 통과 (0.01ms, 10.2MB) 테스트 17 〉 통과 (0.03ms, 10.2MB) 테스트 18 〉 통과 (0.03ms, 10.2MB) 테스트 19 〉 통과 (0.02ms, 10.2MB) 효율성 테스트 테스트 1 〉 통과 (56.14ms, 13.1MB) 테스트 2 〉 통과 (56.68ms, 13.1MB) 테스트 3 〉 통과 (53.73ms, 13MB) 테스트 4 〉 통과 (56.27ms, 13MB) 테스트 5 〉 통과 (45.67ms, 11MB)
흠 그럼 힙큐로? 망함
def solution(pieces, word): from heapq import heappop, heappush queue = [(0, 0)] # counter, index while queue: counter, index = heappop(queue) if index == len(word): return counter for piece in pieces: if word[index:][:len(piece)] == piece: heappush(queue, (counter + 1, index + len(piece))) return -1
테스트 1 〉 통과 (0.04ms, 10.1MB) 테스트 2 〉 통과 (0.46ms, 10.2MB) 테스트 3 〉 통과 (0.01ms, 10.1MB) 테스트 4 〉 통과 (2.44ms, 10MB) 테스트 5 〉 통과 (209.68ms, 12.7MB) 테스트 6 〉 통과 (0.01ms, 10.2MB) 테스트 7 〉 실패 (시간 초과) 테스트 8 〉 실패 (시간 초과) 테스트 9 〉 실패 (시간 초과) 테스트 10 〉 실패 (시간 초과) 테스트 11 〉 실패 (시간 초과) 테스트 12 〉 통과 (0.02ms, 10MB) 테스트 13 〉 통과 (0.12ms, 10.3MB) 테스트 14 〉 통과 (0.13ms, 10.2MB) 테스트 15 〉 통과 (0.06ms, 10.2MB) 테스트 16 〉 통과 (0.01ms, 10.2MB) 테스트 17 〉 통과 (0.01ms, 10MB) 테스트 18 〉 통과 (0.06ms, 10.1MB) 테스트 19 〉 통과 (0.03ms, 10.1MB)
힙큐와 방문 체크로? 망함
def solution(pieces, word): from heapq import heappop, heappush queue = [(0, 0)] # counter, index visited = set() while queue: counter, index = heappop(queue) if index in visited: continue visited.add(index) if index == len(word): return counter for piece in pieces: if word[index:][:len(piece)] == piece: heappush(queue, (counter + 1, index + len(piece))) return -1
정확성 테스트 테스트 1 〉 통과 (0.03ms, 10.2MB) 테스트 2 〉 통과 (0.04ms, 10.2MB) 테스트 3 〉 통과 (0.01ms, 10.3MB) 테스트 4 〉 통과 (0.07ms, 10MB) 테스트 5 〉 통과 (0.08ms, 10.3MB) 테스트 6 〉 통과 (0.01ms, 10.2MB) 테스트 7 〉 통과 (0.55ms, 10.1MB) 테스트 8 〉 통과 (3.41ms, 10.4MB) 테스트 9 〉 통과 (3.69ms, 10.4MB) 테스트 10 〉 통과 (4.26ms, 10.4MB) 테스트 11 〉 통과 (4.76ms, 10.2MB) 테스트 12 〉 통과 (0.01ms, 10.3MB) 테스트 13 〉 통과 (0.03ms, 10MB) 테스트 14 〉 통과 (0.04ms, 10.1MB) 테스트 15 〉 통과 (0.04ms, 10.4MB) 테스트 16 〉 통과 (0.01ms, 10.1MB) 테스트 17 〉 통과 (0.01ms, 10.3MB) 테스트 18 〉 통과 (0.03ms, 10MB) 테스트 19 〉 통과 (0.02ms, 10.2MB) 효율성 테스트 테스트 1 〉 실패 (시간 초과) 테스트 2 〉 실패 (시간 초과) 테스트 3 〉 실패 (시간 초과) 테스트 4 〉 실패 (시간 초과) 테스트 5 〉 실패 (시간 초과)
문제의 조건을 확인한 뒤 풀어봄...
def solution(pieces, word): from heapq import heappop, heappush pieces = set(pieces) queue = [(0, 0)] # counter, index visited = set() while queue: counter, index = heappop(queue) if index in visited: continue visited.add(index) if index == len(word): return counter for i in range(1, 6): if word[index:][:i] in pieces: heappush(queue, (counter + 1, index + i)) return -1
정확성 테스트 테스트 1 〉 통과 (0.02ms, 10.4MB) 테스트 2 〉 통과 (0.05ms, 10.2MB) 테스트 3 〉 통과 (0.01ms, 10.2MB) 테스트 4 〉 통과 (0.08ms, 10.3MB) 테스트 5 〉 통과 (0.09ms, 9.98MB) 테스트 6 〉 통과 (0.01ms, 10.2MB) 테스트 7 〉 통과 (0.19ms, 10.1MB) 테스트 8 〉 통과 (1.69ms, 10.2MB) 테스트 9 〉 통과 (3.54ms, 10.2MB) 테스트 10 〉 통과 (1.89ms, 10.4MB) 테스트 11 〉 통과 (1.97ms, 10.1MB) 테스트 12 〉 통과 (0.02ms, 10.4MB) 테스트 13 〉 통과 (0.03ms, 10.3MB) 테스트 14 〉 통과 (0.05ms, 10.2MB) 테스트 15 〉 통과 (0.03ms, 10.1MB) 테스트 16 〉 통과 (0.01ms, 10.3MB) 테스트 17 〉 통과 (0.02ms, 10.1MB) 테스트 18 〉 통과 (0.02ms, 10.2MB) 테스트 19 〉 통과 (0.02ms, 10.2MB) 효율성 테스트 테스트 1 〉 통과 (60.63ms, 13MB) 테스트 2 〉 통과 (61.44ms, 13MB) 테스트 3 〉 통과 (63.78ms, 13MB) 테스트 4 〉 통과 (68.75ms, 13MB) 테스트 5 〉 통과 (51.65ms, 11MB)
DP 말고는 답이 없구먼...
이라고 생각했지만 실패....def solution(pieces, word): dp = [float('inf') for _ in range(len(word) + 1)] dp[0] = 0 for index, _ in enumerate(word): if dp[index] == float('inf'): continue for piece in pieces: if index + len(piece) <= len(word) and piece == word[index:][:len(piece)]: dp[index + len(piece)] = min(dp[index + len(piece)], dp[index] + 1) return dp[-1] if dp[-1] != float('inf') else -1
채점을 시작합니다. 정확성 테스트 테스트 1 〉 통과 (0.02ms, 10.1MB) 테스트 2 〉 통과 (0.04ms, 10.1MB) 테스트 3 〉 통과 (0.01ms, 10.1MB) 테스트 4 〉 통과 (0.10ms, 10.2MB) 테스트 5 〉 통과 (0.10ms, 9.93MB) 테스트 6 〉 통과 (0.01ms, 9.95MB) 테스트 7 〉 통과 (0.71ms, 10.1MB) 테스트 8 〉 통과 (4.94ms, 10MB) 테스트 9 〉 통과 (5.28ms, 10.1MB) 테스트 10 〉 통과 (5.85ms, 10.1MB) 테스트 11 〉 통과 (12.74ms, 10.1MB) 테스트 12 〉 통과 (0.02ms, 10.2MB) 테스트 13 〉 통과 (0.05ms, 10.2MB) 테스트 14 〉 통과 (0.04ms, 10.1MB) 테스트 15 〉 통과 (0.03ms, 10.2MB) 테스트 16 〉 통과 (0.01ms, 10.2MB) 테스트 17 〉 통과 (0.02ms, 10.1MB) 테스트 18 〉 통과 (0.03ms, 9.96MB) 테스트 19 〉 통과 (0.02ms, 10.1MB) 효율성 테스트 테스트 1 〉 실패 (시간 초과) 테스트 2 〉 실패 (시간 초과) 테스트 3 〉 실패 (시간 초과) 테스트 4 〉 실패 (시간 초과) 테스트 5 〉 실패 (시간 초과)
반응형