파이썬으로 풀어보는 단어 분할 II(Word Break II): 가능한 모든 문장 찾기

문제 개요

비어 있지 않은 문자열 s와 단어 목록을 담고 있는 사전 wordDict가 주어집니다. 문자열 s에 공백을 삽입하여 각 단어가 사전에 등록된 유효한 단어가 되도록 문장을 구성하고, 만들 수 있는 모든 가능한 문장을 찾아야 합니다.

예를 들어 문자열이 "appleraincoat"이고 사전이 ["app", "apple", "rain", "coat", "raincoat"]라고 한다면, 만들 수 있는 문장은 다음과 같습니다.

apple rain coat
apple raincoat

해결 전략: 재귀 + 메모이제이션

이 문제는 백트래킹(backtracking)과 메모이제이션(memoization)을 결합하면 효율적으로 풀 수 있습니다. 이미 계산한 부분 문자열의 결과를 캐싱해 두면 동일한 하위 문제를 반복해서 풀 필요가 없어 실행 시간이 크게 줄어듭니다.

알고리즘의 동작 순서는 다음과 같습니다.

결과를 저장할 맵 memo를 생성합니다.
문자열과 wordDict를 인자로 받는 solve 메서드를 정의합니다.
s가 빈 문자열이면 빈 리스트를 반환합니다.
s가 memo에 이미 존재하면 캐시된 값 memo[s]를 그대로 반환합니다.
결과를 담을 배열 ret을 생성합니다.
i를 1부터 s의 길이까지 반복하며 다음을 수행합니다.
- s의 인덱스 0부터 i-1까지의 접두사가 wordDict에 존재하는지 확인합니다.
- 존재한다면, 남은 부분(s[i:])에 대해 solve를 재귀 호출합니다.
- 접두사와 재귀 결과를 공백으로 연결한 뒤 앞뒤의 불필요한 공백을 제거하고 ret에 추가합니다.
memo[s] := ret으로 캐싱한 뒤 반환합니다.

파이썬 구현 예제

다음 코드를 통해 실제 동작을 확인해 보겠습니다.

class Solution(object):
    def wordBreak(self, s, wordDict):
        self.memo = {}
        wordDict = set(wordDict)
        return self.solve(s, wordDict)

    def solve(self, s, wordDict):
        if not s:
            return ['']
        if s in self.memo:
            return self.memo[s]
        ret = []
        for i in range(1, len(s) + 1):
            if s[:i] in wordDict:
                for j in self.solve(s[i:], wordDict):
                    ret.append((s[:i] + " " + j).strip())
        self.memo[s] = ret
        return self.memo[s]

ob = Solution()
print(ob.wordBreak("appleraincoat", ["app", "apple", "rain", "coat", "raincoat"]))

입력

"appleraincoat"
["app","apple","rain","coat","raincoat"]

출력

['apple rain coat', 'apple raincoat']

동작 원리 살펴보기

코드의 핵심 포인트는 두 가지입니다.

set 변환: wordDict = set(wordDict)로 사전을 집합으로 바꾸면 특정 단어가 포함되어 있는지 평균 O(1) 시간에 확인할 수 있습니다.
메모이제이션: 동일한 부분 문자열에 대한 결과를 self.memo에 저장해 두므로 중복된 재귀 호출을 건너뛰게 되고, 전체 탐색 범위가 크게 줄어듭니다.

또한 빈 문자열에 대해 ['']를 반환하도록 처리하면 마지막 단어 뒤에 붙는 불필요한 공백을 strip()으로 깔끔하게 제거할 수 있습니다. 이처럼 재귀적 분할과 캐싱을 함께 활용하면, 기하급수적으로 늘어날 수 있는 조합의 수를 관리하면서도 모든 유효한 문장을 빠짐없이 찾아낼 수 있습니다.