[백준 BOJ / Python] 1148번 단어 만들기

문제

3x3 퍼즐판이 주어졌을 때, 퍼즐판의 알파벳을 사용하여 만들 수 있는 단어의 수를 알파벳별로 계산하고, 단어 수의 최솟값과 최댓값에 해당하는 알파벳을 출력하는 문제이다.

풀이

• 퍼즐의 알파벳들과 각 단어의 알파벳들의 비교하여 만들 수 있는 단어인지 파악하고, 퍼즐의 각 알파벳이 총 몇 개의 단어를 만드는데 사용될 수 있는지 세면 최솟값과 최댓값을 구할 수 있다.
• 먼저 단어 사전의 단어들의 알파벳 빈도 딕셔너리로 변환하여 저장한다. (중복 값이 있을 수 있음을 고려) 
• 퍼즐 정보를 하나씩 받으면서 퍼즐의 알파벳 빈도 딕셔너리를 생성한다.
• 단어 사전의 단어들과 퍼즐을 비교하여 퍼즐을 통해 만들 수 있는 단어인지 확인한다.
  • 퍼즐 알파벳의 빈도가 단어 알파벳의 빈도보다 작으면 만들 수 없는 단어이다.
• 만들 수 있는 단어라면, 단어 구성 사용된 알파벳들에 대하여 단어 생성 빈도(puzzle_count)를 1씩 올린다.
• 최종적으로 만들 수 있는 단어의 개수가 최소인 알파벳들과 최솟값, 최대인 알파벳들과 최댓값을 출력한다.

Python 코드

import sys
input = sys.stdin.readline

# 단어를 알파벳 빈도 딕셔너리로 변환하여 저장
def add_word(word):
    temp = dict()
    for x in word:
        if x in temp:
            temp[x] += 1
        else:
            temp[x] = 1
    words_dict[word] = temp
    return

# 퍼즐로 단어를 만들 수 있는지 확인
def can_make_word(puzzle, word):
    for x in word:
        if word[x] > puzzle.get(x, 0):
            return False
    return True

# 결과 출력 함수
def print_answer(puzzle_count):
    ans = list(puzzle_count.items())
    ans.sort(key = lambda x: (x[1],x[0]))
    min_, max_ = ans[0][1], ans[-1][1]
    min_alpha, max_alpha = "",""
    for x, cnt in ans:
        if cnt == min_:
            min_alpha += x
        if cnt == max_:
            max_alpha += x
    print(min_alpha, min_, max_alpha, max_)

# 단어 입력
words_dict = dict()
while True:
    word = input().strip()
    if word == "-":
        break
    if word in words_dict:
        continue
    add_word(word)

# 퍼즐 입력
while True:
    puzzle = input().strip()
    if puzzle == "#":
        break
        
    # 퍼즐의 알파벳 빈도 딕셔너리 생성
    puzzle_dict = dict()
    for x in puzzle:
        if x in puzzle_dict:
            puzzle_dict[x] += 1
        else:
            puzzle_dict[x] = 1

    # 퍼즐에 포함된 단어의 알파벳 개수 계산
    puzzle_count = {t:0 for t in puzzle_dict.keys()}
    for word_dict in words_dict.values():
        if can_make_word(puzzle_dict, word_dict):
            for x in word_dict:
                puzzle_count[x] += 1

    # 결과 출력
    print_answer(puzzle_count)

 

문제출처

https://www.acmicpc.net/problem/1148