title: "[프로그래머스] 단어 퍼즐 Python 파이썬 해설 (Level 4) - 이도훈"
cleanUrl: "programmers/12983"
description: "프로그래머스 Level 4 문제 [단어 퍼즐]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

strs 내의 단어 조각들이 t의 어떤 prefix의 suffix인지를 미리 파악해두고, DP를 활용하면 됩니다.

이 때 주의할 점은 단순히 t의 모든 prefix + strs 내의 단어 조각들을 순회하면서 .endswith를 활용하여 prefix-suffix 매칭 여부를 확인하면 시간 초과가 납니다. 해시를 활용해서 단어 조각들과 각 prefix의 길이 최대 5까지의 suffix가 매칭되는지 아닌지 O(1)에 파악하면 통과 가능합니다.

DP는 간단히 설명하면

• dp[i] = i번째 prefix 까지 단어 조각을 최소로 사용해서 만들 때의 단어 조각 수
• dp[i] = min(dp[i - 단어 조각 j의 길이] + 1) (단, 단어 조각 j는 i 번째 prefix의 suffix)

코드

from math import inf
from collections import defaultdict

def solution(strs, t):
    lengths = [len(s) for s in strs]
    
    # 효율성 테스트가 빡빡한 문제입니다.
    # .endswith로 suffix와 단어 조각을 하나하나 비교해도 되겠지만
    # 그러면 시간초과가 납니다.
    # 단어 조각의 길이가 5라는 점을 이용하면, suffix에 매칭되는
    # 단어 조각이 최대 5개밖에 안 됨을 알 수 있습니다. 이를 이용합니다.
    str2j = {s:j for j, s in enumerate(strs)}
    
    # suffixes[i] = t의 i번째 prefix (=t[:i])의 suffix에 매칭되는
    # 단어 조각들의 인덱스를 모은 리스트입니다.
    suffixes = defaultdict(list)
    for i in range(1, len(t) + 1):
        tsuffix = t[:i]
        for k in range(1, min(i+1, 5+1)):
            if tsuffix[i-k:i] in str2j:
                suffixes[i].append( str2j[tsuffix[i-k:i]] )
    
    dp = [0] + [inf] * len(t)
    for i in range(1, len(t) + 1):
        mn = inf
        for j in suffixes[i]:
            if dp[i-lengths[j]] + 1 < mn:
                mn = dp[i-lengths[j]] + 1
        
        dp[i] = mn
            
    return dp[-1] if dp[-1] != inf else -1

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges