문자열이 단어 목록으로 나누어지는지 확인하는 파이썬 프로그램
단어 목록(words)과 공백이 포함되지 않은 하나의 문자열 s가 주어졌다고 가정해 보겠습니다. 이때 확인해야 할 것은 문자열 s가 주어진 단어 목록에 있는 단어들의 조합으로 완전히 분해될 수 있는지 여부입니다.
예를 들어, words = ["love", "python", "we", "programming", "language"]이고 s = "welovepythonprogramming"이라면, 이 문자열은 "we" + "love" + "python" + "programming"으로 나눌 수 있으므로 출력 결과는 True가 됩니다.
해결 접근 방식
이 문제는 재귀(recursion)를 활용하여 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.
- words에 중복을 제거한 모든 고유 단어를 담은 집합(set)을 저장합니다.
- 인덱스 i를 매개변수로 받는 rec() 함수를 정의합니다.
- i가 문자열 s의 길이와 같다면 True를 반환합니다. 즉, 문자열 끝까지 성공적으로 도달했다는 의미입니다.
- 빈 문자열 acc를 초기화합니다.
- j를 i부터 s의 길이까지 반복하며 다음을 수행합니다.
- acc에 s[j]를 이어 붙여 부분 문자열을 만듭니다.
- acc가 words 집합에 존재한다면, rec(j + 1)을 호출한 결과가 True인지 확인하고, 참이라면 True를 반환합니다.
- 모든 경우를 확인한 후에도 분해에 실패하면 False를 반환합니다.
- 메인 메서드에서 rec(0)을 호출하고 그 결과를 반환합니다.
더 나은 이해를 돕기 위해 다음 구현 예제를 살펴보겠습니다.
구현 예제
class Solution:
def solve(self, words, s):
words = set(words)
def rec(i=0):
if i == len(s):
return True
acc = ""
for j in range(i, len(s)):
acc += s[j]
if acc in words:
if rec(j + 1):
return True
return False
return rec()
ob = Solution()
words = ["love", "python", "we", "programming", "language"]
s = "welovepythonprogramming"
print(ob.solve(words, s))
입력
["love", "python", "we", "programming", "language"], "welovepythonprogramming"
출력
True
동작 원리 요약
rec() 함수는 현재 위치 i에서 시작하는 부분 문자열을 한 글자씩 늘려가며 words 집합에 존재하는지 검사합니다. 일치하는 단어를 찾으면 그 단어 다음 위치부터 다시 재귀 호출을 진행하고, 문자열의 끝에 도달하면 전체 분해가 성공한 것으로 판단합니다. 이러한 백트래킹 방식 덕분에 어떤 위치에서 단어 조합이 막히더라도 다른 가능성을 계속 탐색할 수 있습니다.