이 튜토리얼에서는 주어진 문자들만 사용하여 만들 수 있는 모든 단어를 찾는 방법을 다룹니다. 먼저 예시 테스트 케이스를 통해 문제를 명확히 이해해 보겠습니다.
입력:
words = ["hi", "hello", "bye", "good"]
characters = ["h", "i", "b", "y", "e"]
출력:
hi
bye
위 예시에서 "hi"와 "bye"는 주어진 문자 h, i, b, y, e만으로 구성되어 있으므로 만들 수 있습니다. 반면 "hello"에는 l이 없고, "good"에는 g, o, d가 없기 때문에 제외됩니다.
그럼 아래 단계를 따라 목표를 달성해 보겠습니다.
알고리즘
1. 단어 목록(words)과 문자 목록(characters)을 초기화한다.
2. 단어의 각 문자 개수를 담은 딕셔너리를 반환하는 함수를 작성한다.
2.1. 빈 딕셔너리를 초기화한다.
2.2. 단어를 순회하며 해당 문자가 이미 있으면 개수를 1 증가시키고,
없으면 1로 초기화한다.
2.3. 반복이 끝나면 딕셔너리를 반환한다.
3. 단어 목록을 순회한다.
3.1. 플래그(flag) 변수를 1로 초기화한다.
3.2. 위에서 작성한 함수로 문자 개수를 구해 변수에 저장한다.
3.3. 반환된 딕셔너리를 순회한다.
3.3.1. 키(문자)가 characters에 존재하는지 확인한다.
3.3.1.1. 존재하지 않으면 플래그를 0으로 설정한다.
3.3.2. 존재하면 characters 내 문자의 개수와 딕셔너리의 개수를 비교한다.
3.3.2.1. 개수가 다르면 플래그를 0으로 설정한다.
3.4. 플래그가 1이면 해당 단어를 출력한다.
이제 위 알고리즘을 실제 코드로 구현해 보겠습니다.
구현 예제
## 리스트 초기화
words = ["hi", "hello", "bye", "good"]
characters = ["h", "i", "b", "y", "e"]
## 각 문자의 개수를 담은 딕셔너리를 반환하는 함수
def char_count(word):
## 빈 딕셔너리 초기화
counts = {}
## 문자별 빈도수 계산
for char in word:
## 이미 존재하면 1 증가, 없으면 1로 생성
counts[char] = counts.get(char, 0) + 1
## 딕셔너리 반환
return counts
## 단어 목록 순회
for word in words:
## 플래그를 1로 초기화
flag = 1
## char_count() 함수로 문자 개수 조회
chars = char_count(word)
## 각 문자 검사
for key in chars:
## characters에 문자가 없는 경우
if key not in characters:
flag = 0
else:
## 필요한 개수와 가진 개수 비교
if characters.count(key) != chars[key]:
flag = 0
## 모든 검사를 통과한 경우에만 출력
if flag == 1:
print(word)
참고: 단어 출력 코드(if flag == 1:)는 반드시 내부 반복문이 끝난 뒤, 즉 모든 문자 검사가 완료된 후에 실행되어야 합니다. 내부 반복문 안에 넣으면 같은 단어가 여러 번 출력될 수 있습니다.
실행 결과
위 프로그램을 실행하면 다음과 같은 결과를 얻을 수 있습니다.
hi
bye
더 간결한 방법: collections.Counter 활용
파이썬 표준 라이브러리의 collections.Counter를 사용하면 같은 로직을 훨씬 짧은 코드로 구현할 수 있습니다. Counter끼리 뺄셈을 하면 필요한 문자 중 부족한 것만 남게 되는데, 그 결과가 비어 있다면 해당 단어를 만들 수 있다는 의미입니다.
from collections import Counter
words = ["hi", "hello", "bye", "good"]
characters = ["h", "i", "b", "y", "e"]
## 사용 가능한 문자의 빈도수
char_pool = Counter(characters)
for word in words:
## 부족한 문자가 없으면(결과가 비어 있으면) 출력
if not (Counter(word) - char_pool):
print(word)
이 방법은 직접 빈도수를 계산하는 코드보다 가독성이 좋고 성능 면에서도 유리합니다.
마무리
지금까지 주어진 문자로 만들 수 있는 단어를 찾는 두 가지 방법을 살펴보았습니다. 핵심은 각 문자의 빈도수를 비교하는 것이며, 이는 스크래블(Scrabble) 같은 단어 게임이나 아나그램 문제를 풀 때 자주 활용되는 기법입니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.