View in English →

Code › algorithm-study

LeetCode 139 - Word Break

문자열을 단어 사전으로 나눌 수 있는지 DP로 판별한 Python 풀이

algorithmleetcodedynamic-programmingstringpythonlearning

Medium 난이도의 DP 문제다. 문자열 s와 단어 목록 wordDict가 주어졌을 때, s 전체를 사전에 있는 단어들의 조합으로 나눌 수 있는지 판별한다. 이번 문제는 혼자서 풀이를 끌어내지 못했고, 풀이를 본 뒤 dp 배열을 체크포인트처럼 쓰는 방식을 배웠다.

문제 링크 & 설명

  • 문제 링크: 139. Word Break
  • 요약: 문자열 s와 단어 사전 wordDict가 주어졌을 때, 사전에 있는 단어들을 하나 이상 이어 붙여 s를 만들 수 있으면 true를 반환하는 문제다. 같은 단어는 여러 번 사용할 수 있다.

예를 들어 s가 leetcode이고 wordDict가 ["leet", "code"]라면 leet와 code로 나눌 수 있으므로 true다. 반대로 s가 catsandog이고 사전에 cats, dog, sand, and, cat이 있어도 전체 문자열을 빈틈없이 나누는 조합이 없으므로 false가 된다.

접근 방법

처음에는 어디서 잘라야 할지 기준을 잡지 못했다. 앞에서부터 가능한 단어를 고르면 될 것 같기도 하고, 뒤에서부터 맞춰볼 수도 있을 것 같았는데, 어떤 선택이 이후의 가능성을 보장하는지는 바로 보이지 않았다.

풀이를 보면서 핵심은 특정 위치까지 이미 만들 수 있는지를 저장하는 것이라고 이해했다. dp[i]는 s의 앞에서부터 i번째 문자 직전까지, 즉 s[:i]를 wordDict의 단어들로 만들 수 있는지를 뜻한다. 그래서 dp 배열의 길이는 문자열 길이보다 하나 길고, dp[0]은 빈 문자열을 만들 수 있다는 출발점이라 True로 둔다.

dp = [False] * (s_len + 1)
dp[0] = True

이 dp[0]이 없으면 첫 단어를 시작할 기준점이 사라진다. 예를 들어 leet가 사전에 있을 때 s[0:4]를 확인하려면 j가 0인 상태에서 dp[0]이 True여야 한다. 빈 문자열을 실제 단어로 취급한다는 뜻은 아니고, 첫 번째 유효한 조각이 시작될 수 있는 체크포인트를 열어두는 역할이다.

그다음에는 i를 1부터 s_len까지 늘려가며, 그 위치에서 끝나는 마지막 단어를 찾는다. j는 마지막 단어가 시작되는 split index다. dp[j]가 True라면 s[:j]까지는 이미 만들 수 있고, 동시에 s[j:i]가 word_set 안에 있으면 s[:i]도 만들 수 있다.

for i in range(1, s_len + 1):
    for j in range(i):
        if dp[j] and s[j:i] in word_set:
            dp[i] = True

말로 풀면 s를 한 번에 전부 자르는 문제가 아니라, 이미 가능한 지점에서 다음 단어 하나를 붙여 도달 가능한 새 지점을 표시하는 방식이다. dp[j]가 True인 지점만 다음 단어를 시작할 수 있는 체크포인트가 된다.

wordDict는 set으로 바꿔서 membership check를 빠르게 했다. list 상태로 매번 단어를 찾으면 사전의 단어 수만큼 비교가 필요하지만, set을 쓰면 평균적으로 빠르게 존재 여부를 확인할 수 있다. 다만 여기서도 Python 문자열 slicing 비용은 따로 봐야 한다.

트러블 슈팅

이 문제에서 가장 헷갈렸던 부분은 dp[i]가 단어 하나의 유효성을 뜻하는 게 아니라는 점이었다. dp[i]는 s[:i] 전체를 만들 수 있는지에 대한 값이다. 마지막 조각인 s[j:i]가 사전에 있어도, 그 앞부분 s[:j]를 만들 수 없다면 그 분할은 사용할 수 없다.

예를 들어 어떤 s[j:i]가 word_set 안에 있어도 dp[j]가 False라면, 그 단어 앞까지 이어지는 유효한 경로가 없다는 뜻이다. 그래서 조건은 항상 dp[j]와 s[j:i] in word_set을 같이 봐야 한다.

또 하나는 시간복잡도였다. 겉으로는 i와 j의 이중 반복이라 O(n²)처럼 보이는데, Python에서 s[j:i]는 새 문자열을 만든다. 이 slicing은 조각의 길이에 비례하는 시간이 들고, 새로 만든 문자열을 set에서 찾을 때도 그 문자열의 해시 계산이 필요하다. 모든 i, j 조합에서 길이가 다른 substring을 만들기 때문에 전체 시간은 O(n³)으로 잡는 게 맞다.

복잡도 분석

  • 시간 복잡도: O(n³ + L)

    • n은 s의 길이이고, L은 wordDict에 들어 있는 전체 문자 수다. wordDict를 set으로 만드는 데 O(L)이 들고, DP에서는 O(n²)개의 j, i 조합을 확인한다. 각 확인에서 s[j:i] slicing과 membership check를 위한 문자열 해시 계산이 substring 길이에 비례하므로 전체 substring 처리 비용은 O(n³)이다.

  • 공간 복잡도: O(n + M)

    • M은 wordDict의 단어 수다. dp 배열은 O(n)을 사용하고, word_set은 기존 문자열 객체의 참조를 O(M)개 저장한다. slicing으로 만들어지는 임시 문자열은 한 번에 최대 O(n)까지 생길 수 있으므로 추가 공간은 O(n + M)이다.

구현 코드

from typing import List

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        word_set = set(wordDict)
        s_len = len(s)
        dp = [False] * (s_len + 1)
        dp[0] = True

        for i in range(1, s_len + 1):
            for j in range(i):
                if dp[j] and s[j:i] in word_set:
                    dp[i] = True

        return dp[-1]

요약 및 회고

이번 문제는 혼자서 DP 상태를 정의하지 못했고, 풀이를 보고 나서야 dp[i]를 s[:i]의 가능 여부로 두는 방식이 이해됐다. 단어를 하나씩 고르는 문제가 아니라, 이미 도달 가능한 문자열 위치를 기준으로 다음 단어를 붙일 수 있는지 확인하는 문제였다.

특히 dp[0]이 빈 문자열을 뜻하는 시작 체크포인트라는 점, j가 마지막 단어의 시작점을 정한다는 점을 잡고 나니 코드가 훨씬 단순하게 보였다. 그리고 Python에서는 이중 반복 안의 slicing까지 시간복잡도에 포함해야 한다. 같은 DP 풀이여도 언어의 문자열 처리 비용을 빼면 분석이 틀어질 수 있다는 걸 다시 확인한 문제였다.