유효한 단어들의 목록과 하나의 문자열 s가 주어졌을 때, s에서 시작해 한 번에 한 글자씩 제거하면서도 그 결과가 여전히 목록에 포함된 유효한 단어가 되도록 만들 수 있는 가장 긴 감소 단어 체인의 길이를 구하는 것이 이번 문제의 목표입니다.
문제 이해하기
예를 들어, words = ["lii", "limit", "limi", "li", "coffee", "jug", "pool", "type"]이고 s = "limit"라고 가정해 보겠습니다. 이때 출력은 4가 됩니다. "limit"에서 시작해 다음과 같은 체인을 만들 수 있기 때문입니다.
"limit" → "limi" → "lii" → "li"
각 단계마다 글자를 하나씩 제거하지만, 결과로 나오는 단어는 반드시 주어진 목록 안에 존재해야 한다는 점이 핵심입니다.
풀이 접근 방식
이 문제는 재귀 호출을 활용해 자연스럽게 해결할 수 있습니다. 전체적인 동작 흐름은 다음과 같습니다.
- solve()라는 함수를 정의합니다. 이 함수는 words와 s를 인자로 받습니다.
- max_num을 0으로 초기화합니다.
- words의 각 단어 i에 대해 다음을 수행합니다.
- i가 s와 같다면, j를 0부터 s의 길이 - 1까지 반복하면서
- j번째 글자를 제거한 새로운 문자열로 solve()를 재귀 호출하고, 반환값에 1을 더한 것과 기존 max_num 중 더 큰 값을 max_num에 저장합니다.
- 모든 반복이 끝나면 max_num을 반환합니다.
예제 코드
class Solution:
def solve(self, words, s):
max_num = 0
for i in words:
if i == s:
for j in range(len(s)):
max_num = max(1 + self.solve(words, s[:j] + s[j + 1 :]), max_num)
return max_num
ob = Solution()
words = ["lii", "limit", "limi", "li", "coffee", "jug", "pool", "type"]
s = "limit"
print(ob.solve(words, s))입력
["lii", "limit", "limi", "li", "coffee", "jug", "pool", "type"], "limit"
출력
4
동작 원리 살펴보기
이 알고리즘은 현재 문자열과 일치하는 단어를 목록에서 발견하면, 가능한 모든 위치의 글자를 하나씩 제거해 보며 각 경우에 대해 같은 과정을 다시 반복합니다. 더 이상 체인을 확장할 수 없으면 0을 반환하고, 호출 스택을 거슬러 올라가며 매 단계마다 1씩 더해져 최종 체인 길이가 계산됩니다.
다만 이 방식은 모든 경우를 완전 탐색하므로 입력이 커지면 시간 복잡도가 지수적으로 증가할 수 있습니다. 실무 환경에서는 메모이제이션(memoization)을 적용해 중간 결과를 캐싱하거나, 단어 목록을 집합(set) 또는 딕셔너리(dict)로 변환해 조회 속도를 높이면 성능을 크게 개선할 수 있습니다.