단어 목록(words)과 문자열(letters)이 주어졌을 때, 주어진 문자들을 재배열하여 만들 수 있는 가장 긴 단어의 길이를 찾는 프로그램을 작성해야 합니다. 여기서 letters에는 별표(*)가 포함될 수 있으며, 별표는 어떤 문자와도 매칭되는 와일드카드 역할을 합니다. 또한 주어진 모든 문자를 반드시 사용할 필요는 없습니다.
예를 들어, 입력이 words = ["prince", "rice", "price", "limit", "hello"], letters = "*r**ce*"라고 가정해 보겠습니다. 이 경우 출력은 6이 됩니다. 별표 덕분에 부족한 문자(p, i, n 등)를 채울 수 있어 가장 긴 단어인 "prince"(길이 6)를 만들 수 있기 때문입니다.
문제 해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다:
- has := letters에 포함된 각 문자의 빈도수를 저장하는 카운터(Counter)
- valid() 함수를 정의합니다. 이 함수는 검사할 단어 s를 인자로 받습니다.
- need := s에 포함된 각 문자의 빈도수를 저장하는 카운터
- extra := need의 각 문자에 대해 max(0, need[char] - has[char]) 값들의 합, 즉 단어를 완성하기 위해 부족한 문자의 개수
- extra가 has["*"]보다 작거나 같으면 True를 반환합니다. (부족한 문자를 별표로 모두 대체할 수 있다는 의미)
- 메인 메서드에서는 words 중 valid 조건을 통과한 단어들의 길이 중 최댓값을 반환합니다.
구현 예제
더 나은 이해를 위해 파이썬 구현 코드를 살펴보겠습니다:
from collections import Counter class Solution: def solve(self, words, letters): has = Counter(letters) def valid(s): need = Counter(s) extra = sum([max(0, need[char] - has[char]) for char in need]) return extra <= has["*"] return max([len(word) for word in words if valid(word)]) ob = Solution() words = ["prince", "rice", "price", "limit", "hello"] letters = "*r**ce*" print(ob.solve(words, letters))
입력
["prince", "rice", "price", "limit", "hello"], "*r**ce*"
출력
6
코드 설명
파이썬의 Counter는 문자열 내 각 문자의 등장 횟수를 자동으로 계산해 주는 편리한 도구입니다. valid() 함수는 단어를 만들기 위해 필요하지만 현재 가지고 있지 않은 문자의 개수(extra)를 계산한 뒤, 이 부족분이 별표(*)의 개수로 커버 가능한지 확인합니다. 각 단어를 한 번씩만 검사하면 되므로 전체 시간 복잡도는 단어들의 총 길이에 비례하며 매우 효율적입니다.