[프로그래머스] 단어 퍼즐

문제 요약

주어진 단어 조각을 원하는 만큼 사용해 문자열 t를 완성한다.

문자열을 완성하는 데 필요한 단어 조각 수의 최솟값을 구하고, 만들 수 없다면 -1을 반환한다.

핵심 아이디어

dp[i]를 t의 앞에서부터 i글자까지 완성하는 데 필요한 최소 조각 수라고 정의한다.

dp[0] = 0

어떤 위치 i까지 만들 수 있고, 그 위치부터 시작하는 조각 piece가 t와 일치한다면 다음 위치를 갱신한다.

dp[i + len(piece)] = min(
    dp[i + len(piece)],
    dp[i] + 1
)

각 조각을 무한히 사용할 수 있으므로, 같은 조각을 여러 위치에서 반복해서 사용해도 된다.

풀이 과정

1. 길이가 len(t) + 1인 DP 배열을 만들고, 도달할 수 없는 값은 큰 값으로 초기화한다.
2. dp[0] = 0으로 시작한다.
3. 문자열의 각 위치에서, 해당 위치부터 일치하는 모든 단어 조각을 확인한다.
4. 일치하는 조각의 끝 위치를 최소 조각 수로 갱신한다.
5. dp[len(t)]가 여전히 큰 값이면 -1을 반환한다.

Python 코드

def solution(strs, t):
    length = len(t)
    infinity = length + 1

    # dp[i]: t의 앞 i글자를 만드는 데 필요한 최소 조각 수
    dp = [infinity] * (length + 1)
    dp[0] = 0

    for start in range(length):
        if dp[start] == infinity:
            continue

        for piece in strs:
            end = start + len(piece)

            if end <= length and t.startswith(piece, start):
                dp[end] = min(dp[end], dp[start] + 1)

    return -1 if dp[length] == infinity else dp[length]

예시

strs = ["ba", "na", "n", "a"], t = "banana"인 경우를 보자.

dp[0] = 0
"ba" 사용  -> dp[2] = 1
"na" 사용  -> dp[4] = 2
"na" 사용  -> dp[6] = 3

따라서 "ba" + "na" + "na"로 문자열을 만들 수 있고, 필요한 조각 수는 3이다.

시간 복잡도

N을 t의 길이, S를 단어 조각 개수, L을 조각의 최대 길이라고 하자.

각 위치에서 모든 조각을 확인하고, 문자열 비교는 최대 L글자를 확인한다.

• 시간 복잡도: O(N * S * L)
• 공간 복잡도: O(N)

이 문제에서는 N <= 20,000, S <= 100, L <= 5이므로 충분히 빠르게 동작한다.

정리

문자열을 앞에서부터 완성하는 최소 비용 문제로 바꾸면 된다. dp[i]가 도달 가능한 위치인지 확인하고, 그 위치에 이어 붙일 수 있는 단어 조각으로 다음 상태를 갱신한다.