[정글 코어타임] - [리트코드] 139. Word Break

 

이번 문제는 문자열 s를 사전에 있는 단어들로 끊어서 만들 수 있는지 판별하는 Word Break 문제입니다. 얼핏 보면 문자열 탐색 문제 같지만, 실제로는 앞에서부터 어디까지 만들 수 있는지를 저장해 가는 전형적인 DP 문제입니다. 이 글에서는 문제 아이디어, 점화식, 시각화, 예제 분석, 그리고 코드 한 줄 설명까지 한 번에 정리해보겠습니다.

핵심 요약

• 문자열을 앞에서부터 잘라 보면서 만들 수 있는 위치를 체크합니다.
• dp[i]는 s의 앞 i글자까지 만들 수 있는지를 의미합니다.
• 어떤 j에 대해 dp[j] == True 이고 s[j:i] 가 사전에 있으면 dp[i] = True 입니다.
• 핵심은 이전까지 만들 수 있었는가 + 이번 조각이 사전에 있는가 입니다.
• 시간 복잡도는 기본적으로 O(n²) 탐색 구조를 가집니다.

1. 문제 설명

문자열 s 와 단어 사전 wordDict 가 주어질 때, s를 공백으로 나눈 여러 단어들의 조합으로 만들 수 있으면 true, 만들 수 없으면 false 를 반환하는 문제입니다.

예를 들어 s = "leetcode", wordDict = ["leet", "code"] 라면
leet + code 로 분리할 수 있으므로 정답은 true 입니다.

2. 왜 DP로 푸는가?

이 문제에서 중요한 건 문자열 전체를 한 번에 보는 것이 아니라, 앞부분이 만들어지는지 여부를 차례대로 쌓아 간다는 점입니다.

만약 s의 앞 j글자까지는 만들 수 있었고, 그 다음 구간 s[j:i] 가 사전에 있는 단어라면, 앞 i글자까지도 만들 수 있습니다. 이런 식으로 이전 상태를 이용해 다음 상태를 판별하므로 DP가 정확하게 들어맞습니다.

3. DP 정의와 점화식

dp[i] 를 s의 앞 i글자를 만들 수 있는지 여부라고 정의합니다.

dp[i] = True, if there exists j < i such that dp[j] is True and s[j:i] is in wordDict

• dp[j] == True : 앞 j글자까지는 이미 만들 수 있음
• s[j:i] in wordDict : j부터 i-1까지의 조각이 사전에 존재함

dp[0] = True

빈 문자열은 아무 단어도 선택하지 않으면 만들 수 있으므로 시작값은 true 입니다.

4. 시각화로 이해하기

예제 s = "leetcode" 를 기준으로 생각해보겠습니다.

문자열 분해 시각화

""
dp[0] = T

→

"leet"
dp[4] = T

→

"leetcode"
dp[8] = T

DP 배열이 채워지는 흐름

dp[0]
True

dp[1]
False

dp[2]
False

dp[3]
False

dp[4]
True

dp[5]
False

dp[6]
False

dp[7]
False

dp[8]
True

핵심 포인트

dp[4] = True 인 이유는 "leet" 가 사전에 있기 때문입니다. 그리고 그다음 dp[8] = True 가 되는 이유는 dp[4]가 이미 True 이고, 남은 조각 "code" 역시 사전에 있기 때문입니다.

5. 코드

아래 코드는 네가 작성한 구조를 그대로 살리면서, 사전 탐색 속도를 위해 list 대신 set 을 사용하고, 이미 만들 수 있다고 판별되면 더 볼 필요가 없도록 break 를 추가한 버전입니다.

Python

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wordSet = set(wordDict)

        # dp 초기화
        dp = [False] * (len(s) + 1)

        # 시작은 빈 문자열이므로 True
        dp[0] = True

        for i in range(1, len(s) + 1):
            # j는 자를 위치
            for j in range(i):
                if dp[j] and s[j:i] in wordSet:
                    dp[i] = True
                    break

        return dp[len(s)]

6. 코드 한 줄 한 줄 설명

이제 위 코드가 실제로 어떤 의미인지 한 줄씩 나눠서 보겠습니다.

라인	코드	설명
1	class Solution:	리트코드 제출 형식에 맞춘 클래스 선언입니다.
2	def wordBreak(self, s: str, wordDict: List[str]) -> bool:	문자열 s가 wordDict의 단어들로 분리 가능한지 판별하는 함수입니다.
3	wordSet = set(wordDict)	단어 존재 여부를 빠르게 확인하기 위해 리스트를 집합으로 바꿉니다.
4	# dp 초기화	DP 배열을 만들기 전 의미를 적어 둔 주석입니다.
5	dp = [False] * (len(s) + 1)	문자열 길이보다 1칸 더 큰 DP 배열을 만들고, 처음에는 전부 False로 둡니다.
6	# 시작은 빈 문자열이므로 True	초기값 설정 이유를 설명하는 주석입니다.
7	dp[0] = True	아무 글자도 없는 상태는 항상 만들 수 있으므로 True로 시작합니다.
8	for i in range(1, len(s) + 1):	앞 1글자부터 전체 길이까지 차례대로 만들 수 있는지 검사합니다.
9	# j는 자를 위치	문자열을 어디서 끊을지 설명하는 주석입니다.
10	for j in range(i):	0부터 i-1까지 모든 분할 위치를 확인합니다.
11	if dp[j] and s[j:i] in wordSet:	앞 j글자까지 만들 수 있었고, j부터 i까지 자른 조각이 사전에 있으면 앞 i글자까지 만들 수 있다는 뜻입니다.
12	dp[i] = True	현재 길이 i까지 만들 수 있다고 표시합니다.
13	break	이미 True가 되었으면 더 확인할 필요가 없으므로 반복을 종료합니다.
14	return dp[len(s)]	문자열 전체 길이까지 만들 수 있는지를 반환합니다. 이 값이 최종 정답입니다.

7. 예제로 직접 따라가기

예제 1. leetcode

i	가능한 분할	결과
4	"leet"	dp[4] = True
8	dp[4]가 True 이고 "code" 존재	dp[8] = True

따라서 정답은 true 입니다.

예제 2. applepenapple

apple → pen → apple 순서로 잘라낼 수 있으므로 true 입니다. 같은 단어를 여러 번 재사용할 수 있다는 조건도 이 예제에서 확인할 수 있습니다.

예제 3. catsandog

중간까지는 잘리는 것처럼 보여도 마지막에 og 를 만들 방법이 없습니다. 즉, 모든 위치를 확인해도 마지막 dp[len(s)] 가 True가 되지 않으므로 false 입니다.

8. 네 코드와 비교했을 때 포인트

• 원리 자체는 완전히 맞습니다. 네 코드도 DP 접근을 정확히 사용하고 있습니다.
• s[j:i] in wordDict 는 리스트 탐색이라 매번 느릴 수 있어서 set 으로 바꾸면 더 좋습니다.
• dp[i] = True 가 된 순간 더 볼 필요가 없으므로 break 를 넣으면 조금 더 효율적입니다.
• 핵심 사고 방식은 동일합니다. 결국 중요한 건 앞부분이 만들어졌는지와 이번 조각이 사전에 있는지 입니다.

9. 시간 복잡도와 공간 복잡도

• 시간 복잡도: O(n²) 형태로 볼 수 있습니다.
• 공간 복잡도: O(n)

문자열 길이를 n이라고 하면, i와 j를 이중 반복으로 돌기 때문에 기본 구조는 O(n²)입니다. DP 배열 하나를 사용하므로 공간 복잡도는 O(n)입니다.

10. 마무리

Word Break는 처음 보면 백트래킹처럼 느껴질 수 있지만, 사실은 어디까지 만들 수 있는지 저장하는 DP 문제입니다. 이 관점만 잡히면 문제 구조가 굉장히 단순해집니다.

dp[j]가 True이고 s[j:i]가 사전에 있으면 dp[i] = True

한 줄 결론

Word Break는 문자열의 앞부분이 만들어지는지 여부를 저장해 가면서, 사전에 있는 단어로 다음 구간을 이어 붙일 수 있는지 확인하는 대표적인 DP 문제입니다.