문제 설명 및 제한사항
아이디어 및 해결 방법
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
Python
복사
출처
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges