문제 개요
문자열 리스트 words와 문자열 letters가 주어졌을 때, letters에 포함된 문자들을 사용하여 만들 수 있는 words 중 가장 긴 문자열의 길이를 구하는 프로그램을 작성해야 합니다.
단, 다음 두 가지 조건이 있습니다.
- 각 문자는 한 번만 사용할 수 있으며 재사용이 불가능합니다.
- 만들 수 있는 단어가 하나도 없다면 0을 반환합니다.
예시
입력이 다음과 같다고 가정해 보겠습니다.
words = ["dog", "cat", "rat", "bunny", "lion", "bat"] letters = "gabctnyu"
이 경우 출력은 3이 됩니다. 사용 가능한 문자 "gabctnyu"로는 "cat" 또는 "bat"을 만들 수 있으며, 이 단어들의 길이가 3으로 가장 길기 때문입니다.
해결 접근 방법
이 문제는 각 문자의 등장 횟수를 비교하는 방식으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- ref: letters에 포함된 각 문자와 그 빈도수를 저장한 맵(Counter)을 만듭니다.
- max: 결과값을 저장할 변수로 초기값은 0입니다.
- words의 각 단어에 대해 다음을 수행합니다.
- w: 해당 단어의 각 문자와 그 빈도수를 저장한 맵을 만듭니다.
- l: 단어의 길이를 저장합니다.
- counter: 조건을 만족하는 서로 다른 문자의 개수를 세는 변수로 0으로 초기화합니다.
- w의 각 문자 k에 대해, 단어에서 필요한 개수(w[k])가 사용 가능한 개수(ref[k])보다 작거나 같으면 counter를 1 증가시키고, 그렇지 않으면 반복을 중단합니다.
- 반복이 끝난 후, 단어 길이 l이 현재 max보다 크고 w의 서로 다른 문자 수(len(w))가 counter와 같다면(즉, 모든 문자가 조건을 통과했다면) max를 l로 갱신합니다.
- 모든 단어를 확인한 후 max를 반환합니다.
참고: Python의
collections.Counter는 존재하지 않는 키에 대해 0을 반환하므로, 별도의 예외 처리 없이ref[k]를 안전하게 비교할 수 있습니다.
구현 코드
위 알고리즘을 파이썬으로 구현하면 다음과 같습니다.
from collections import Counter
class Solution:
def solve(self, words, letters):
# 사용 가능한 문자의 빈도수 계산
ref = Counter(letters)
max_len = 0
for word in words:
# 현재 단어의 문자 빈도수 계산
w = Counter(word)
l = len(word)
counter = 0
# 필요한 각 문자가 충분히 있는지 확인
for k in w:
if w[k] <= ref[k]:
counter += 1
else:
break
# 모든 문자가 조건을 통과했고, 기존 최대 길이보다 길다면 갱신
if l > max_len and len(w) == counter:
max_len = l
return max_len
ob = Solution()
words = ["dog", "cat", "rat", "bunny", "lion", "bat"]
letters = "gabctnyu"
print(ob.solve(words, letters))실행 결과
입력
["dog", "cat", "rat", "bunny", "lion", "bat"], "gabctnyu"
출력
3
정리
이 풀이의 시간 복잡도는 O(N × M)입니다. 여기서 N은 단어의 개수, M은 단어의 평균 길이입니다. 각 단어마다 Counter를 한 번씩 생성하고 문자 개수만큼만 비교하기 때문에 매우 효율적입니다. 스크래블(Scrabble) 게임처럼 제한된 타일로 만들 수 있는 최장 단어를 찾는 실제 문제에도 동일한 원리가 적용됩니다.