[백준/파이썬] 1148: 단어 만들기

문제 보러 가기!

설명 😎

구현 문제였다!
처음에는 퍼즐판이 주어져서 뭔가 2차원 배열로 풀어야 하나? 했지만, 문제를 찬찬히 읽어보니 아니었다.
표의 정중앙에 있는 글자만 꼭 사용해야 하니까, 그 글자만 중요하게 고려하면 된다.
또 어떤 글자를 정중앙에 놓았을 때 정답 개수가 가장 적게/많게 되는지를 찾아야 한다! 그러니까 각 글자가 사용되는 횟수를 구하면 된다.

퍼즐판의 문자들이 주어질 때, 그 문자를 가지고 사전의 단어를 만들 수 있는지 본다.
만들 수 있다면, 각 글자의 사용 횟수를 1씩 더한다.
사전의 단어를 모두 본 후에, 글자 중에 가장 적게/많이 사용하는 글자(사전순)와 그 개수를 출력하면 된다!!

헷갈렸던 부분 🤔

퍼즐판에서 주어진 문자들을 가지고, 사전의 단어를 만들 수 있는지 체크하는 부분!!
처음에는 set을 이용해서 했다. 퍼즐판에 주어진 문자들도 set 안에 넣고, 사전의 각 단어도 set으로 만들어서 issubset를 이용해서 체크하려고 했다. 그러면.. 중복이 제거되어 버려서 제대로 체크가 안된다. 예를 들어서, 내게 주어진 단어는 abc인데, 사전의 단어는 aabc라면!! 원래는 단어를 못 만드는 것인데, 위 방식 대로 하면 단어를 만드는 것으로 체크하게 된다.

그래서 sorted(list(문자))를 이용했다. 퍼즐판에 주어진 문자들도 정렬하고, 사전의 각 단어들도 정렬해서 문자 하나씩 비교해보면서, 단어가 되는지 체크했다! check함수를 보면 된다 :)

코드 🐱‍🚀

import sys
from collections import defaultdict

input = sys.stdin.readline

my_dict = []


def check(keyword, dictionary):
    keyword_idx = 0
    dictionary_idx = 0
    while keyword_idx < len(keyword) and dictionary_idx < len(dictionary):
        if keyword[keyword_idx] == dictionary[dictionary_idx]:
            keyword_idx += 1
            dictionary_idx += 1
            if keyword_idx == len(keyword):
                return True
        else:
            dictionary_idx += 1
            if dictionary_idx == len(dictionary):
                return False
    return False


while True:
    tmp = input().rstrip()
    if tmp == '-':
        break
    else:
        my_dict.append(sorted(list(tmp)))

while True:
    tmp = input().rstrip()
    sorted_tmp = sorted(list(tmp))
    if tmp == '#':
        break
    else:
        word_use_count = defaultdict(int)
        for word in my_dict:  # 사전의 단어를 하나씩 보면서
            # 그 단어 만들 수 있으면
            # if word.issubset(tmp):
            if check(word, sorted_tmp):
                for w in set(word):
                    word_use_count[w] += 1
    # 0번 등장한 알파벳 고려하기
    for i in set(tmp):
        if i not in word_use_count:
            word_use_count[i] = 0

    # 젤 많이/적게 쓴 알파벳 구하기
    most_popular_cnt = max(word_use_count.values())
    least_popular_cnt = min(word_use_count.values())
    most_popular_alp = []
    least_popular_alp = []
    for key, val in word_use_count.items():
        if val == most_popular_cnt:
            most_popular_alp.append(key)
        if val == least_popular_cnt:
            least_popular_alp.append(key)

    # 출력
    print(''.join(sorted(least_popular_alp)), end=' ')
    print(least_popular_cnt, end=' ')
    print(''.join(sorted(most_popular_alp)), end=' ')
    print(most_popular_cnt)