2017 팁스타운: 단어 퍼즐

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 〉	실패 (시간 초과)