LeetCode

LeetCode 139 Word Break 풀이: 문자열 분할을 확인하는 동적 계획법

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

  • 문제: 139. Word Break
  • 출처: LeetCode
  • 자체 판단 난이도: Level 3

문자열을 앞에서부터 확인하면서 지금까지 만든 접두사가 유효한지를 다음 상태로 전달해야 하는 문제다. 단어를 여러 번 사용할 수 있다는 조건과 가능한 분할 중 하나만 찾으면 된다는 점을 동적 계획법으로 표현해야 하므로 Level 3으로 판단했다.

1. 문제 요약

문자열 s와 사전에 들어 있는 단어 배열 wordDict가 주어진다. s를 사전의 단어들로 공백 없이 이어 붙여 만들 수 있다면 true, 그렇지 않으면 false를 반환한다.

사전의 같은 단어를 여러 번 사용해도 된다.

예를 들어 s = "LeetCode", wordDict = ["leet", "code"]라면 다음처럼 나눌 수 있으므로 true다.

leet | code

반면 s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]에서는 문자열 전체를 사전 단어로 나눌 수 없으므로 false다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

핵심 상태 정의

dp[i]를 문자열 s의 앞에서부터 i글자까지, 즉 s[:i]를 사전 단어들로 분할할 수 있는지 여부라고 정의한다.

빈 문자열은 아무 단어도 사용하지 않고 만들 수 있으므로 dp[0] = True다. 이후 위치 end에서 마지막으로 사용한 단어의 길이를 length라고 하면, 그 단어 앞의 접두사 s[:start]가 이미 만들 수 있고 s[start:end]가 사전에 있어야 한다.

dp[end] = dp[start] and s[start:end] in word_set

여기서 start = end - length다. 가능한 마지막 단어를 하나라도 찾으면 해당 위치의 dp[end]를 True로 확정하고 다음 위치로 넘어간다.

왜 앞에서부터 확인하는가

문자열을 단어 하나씩 재귀적으로 나누면 같은 접두사를 여러 경로에서 반복해서 확인하게 된다. 예를 들어 어떤 위치까지의 분할 가능 여부는 그 뒤에 어떤 단어를 붙이더라도 동일하므로, dp에 한 번 저장해 재사용할 수 있다.

사전은 set으로 변환하기

wordDict를 리스트 그대로 검색하면 단어를 찾을 때마다 모든 단어를 비교해야 한다. set으로 바꾸면 평균적으로 빠르게 포함 여부를 확인할 수 있다. 가장 긴 단어보다 긴 조각은 검사할 필요가 없으므로 max_word_length까지만 확인한다.

3. 문제 해결 코드 (Python)

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

        for end in range(1, len(s) + 1):
            for length in range(1, min(end, max_word_length) + 1):
                start = end - length
                if dp[start] and s[start:end] in word_set:
                    dp[end] = True
                    break

        return dp[len(s)]

문자열의 각 끝 위치에서 최대 max_word_length개의 길이를 확인하므로, 문자열 슬라이싱 비용을 제외한 상태 전이 횟수는 O(n × L)다. 여기서 n은 s의 길이이고 L은 사전에서 가장 긴 단어의 길이다. Python의 s[start:end]는 슬라이스를 새로 만들기 때문에 이를 포함하면 시간 복잡도는 최악의 경우 O(n × L²)로 볼 수 있다. 제한에서 L <= 20이므로 충분히 처리할 수 있다.

dp 배열과 set에 저장되는 사전 단어를 제외한 추가 공간은 O(n)이며, 사전 저장 공간까지 포함하면 O(n + D)다. D는 사전 단어 전체 문자 수다.

4. 오답 접근과 반례

가장 긴 단어부터 고르는 그리디

항상 가장 긴 사전 단어를 먼저 선택하면 뒤쪽 문자열을 만들 수 없는 경우가 생긴다. 다음 입력을 살펴보자.

s = "abc"
wordDict = ["ab", "a", "bc"]

가장 긴 단어인 ab를 먼저 선택하면 남은 c를 만들 수 없어 실패한다. 하지만 a | bc로 나누면 전체 문자열을 완성할 수 있다. 가능한 분할을 비교해야 하므로 단순 그리디만으로는 충분하지 않다.

모든 분할을 재귀로 확인하기

가능한 모든 단어 조합을 재귀적으로 시도하면 같은 위치에서 시작하는 하위 문제가 반복된다. 예를 들어 s의 여러 접두사를 통해 같은 start 위치에 도달할 수 있으므로, 메모이제이션 없이 재귀를 사용하면 경우의 수가 빠르게 증가한다.

dp[0]을 False로 두는 경우

첫 번째 단어 하나만으로 문자열의 시작 부분을 만들려면 빈 접두사가 유효하다는 출발점이 필요하다. dp[0] = False로 시작하면 어떤 단어도 문자열의 첫 위치에서 선택되지 않아 모든 결과가 잘못 False가 된다.

복사해 실행할 테스트

아래 assert를 풀이 코드와 같은 Python 파일에 붙여 실행하면 분할 가능·불가능 사례와 단어 재사용을 확인할 수 있다.

solver = Solution()
assert solver.wordBreak("leetcode", ["leet", "code"]) is True
assert solver.wordBreak("applepenapple", ["apple", "pen"]) is True
assert solver.wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"]) is False
assert solver.wordBreak("aaaa", ["a", "aa"]) is True

5. 공식 예제와 추가 검증

LeetCode 공식 예제 3개와 경계 사례를 Python 3.12.4에서 확인했다.

예제 기대 출력 확인 결과
s="LeetCode", wordDict=["leet","code"] True 통과
s="applepenapple", wordDict=["apple","pen"] True 통과
s="catsandog", wordDict=["cats","dog","sand","and","cat"] False 통과

추가 검증 1: 단어 재사용

입력: s = "aaaa", wordDict = ["a", "aa"]
기대 출력: True
확인 결과: 통과
검증 목적: 같은 사전 단어를 여러 번 사용할 수 있는지 확인

추가 검증 2: 사전에 없는 단어가 포함된 경우

입력: s = "cars", wordDict = ["car"]
기대 출력: False
확인 결과: 통과
검증 목적: 마지막 문자를 완성하지 못하면 False를 반환하는지 확인

추가 검증 3: 여러 분할 중 하나만 성공하는 경우

입력: s = "catsand", wordDict = ["cats", "cat", "sand", "and"]
기대 출력: True
확인 결과: 통과
검증 목적: 가능한 분할을 하나라도 찾으면 True인지 확인

6. 다른 풀이 방식 검색 및 비교

  • Word Break 공식 문제는 사전 단어를 재사용해 문자열 전체를 분할할 수 있는지 묻는다.
  • AlgoMonster의 설명은 접두사별 분할 가능 여부를 저장하는 DP와 단어 집합 조회를 설명한다.

탑다운 재귀에 메모이제이션을 적용하는 방식도 사용할 수 있다. 현재 위치에서 시작하는 문자열을 만들 수 있는지 저장하면 같은 위치를 다시 계산하지 않으므로 동일한 상태 수로 해결된다. 이 글에서는 호출 스택이 필요 없고 dp[0]에서 시작해 문자열 끝까지 상태를 채우는 상향식 방식을 사용했다.

마무리

Word Break는 문자열 자체를 한 번에 판단하기보다, 각 접두사를 사전 단어들로 만들 수 있는지 상태로 저장하는 문제다. dp[0] = True를 출발점으로 두고 마지막 단어를 하나씩 선택해 dp[end]를 갱신하면, 단어 재사용과 여러 분할 가능성까지 자연스럽게 처리할 수 있다.

#동적계획법#LeetCode#난이도 3