[알고리즘/구현] 1148번 : 단어 만들기 - python

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

 

 

---

• 문제
• 소요시간: 75분 30초

---

• 설계하기(접근방법) 

1. 입력받기

20만개 정도가 입력되니 sys를 통해서 입력받자

문자열이니 rstrip을 통해 개행문자를 제거해준다

 

2. 구현하기

아이디에이션에 상당히 애를 먹었다.

 

먼저 20만개의 단어를 검증하려니 딕셔너리가 생각이 났다.

먼저 딕셔너리에 모든 단어를 넣어준다

 

그 다음 주어진 퍼즐의 문자의 조합과 순열로

20만개의 딕셔너리를 검증할 수 있는지 계산해보았다.

 

서로다른 알파벳 9개의 경우 9!이니 시간초과가 나지 않는다.

8개의 경우 9개 중에 8개를 뽑은 후, 8개의 순열을 계산하니 또한 9!으로 시간초과가 나지 않는다.

 

이처럼

조합 및 순열 알파벳 4개부터 9개까지 

itertools의 comb 와 perm으로 for문을 돌리면서

해당 퍼즐 문자들로 가능한 단어 중 딕셔너리에 있는 단어들을 추출한다

 

 

여기서부터는 쉬워진다.

먼저 퍼즐의 문자들을 새로운 딕셔너리에 저장해준다.

 

그 후 추출한 단어장의 알파벳을 set()을 통해 중복을 제거해주고

각 알바벳이 총 몇번 나타나는지 뽑아낸다

 

그러면 가장 적게 쓰이는 알파벳과 많이 쓰이는 알파벳

그리고 쓰인 횟수를 카운팅 할 수 있다

 

sorted lambda를 통해 한번 정렬해주면
위의 결과들이 아래와 같이 출력될것이다

 

LARBITNLI
{'LINT': 1, 'TILL': 1, 'TRILL': 1, 'BRILLIANT': 1}
[['A', 1], ['B', 1], ['N', 2], ['R', 2], ['I', 4], ['L', 4], ['T', 4]]
LEPAPBNNA
{'PALE': 1, 'BANE': 1, 'APPLE': 1}
[['B', 1], ['N', 1], ['L', 2], ['P', 2], ['A', 3], ['E', 3]]
LEPAPBNAM
{'PALE': 1, 'BANE': 1, 'APPLE': 1}
[['M', 0], ['B', 1], ['N', 1], ['L', 2], ['P', 2], ['A', 3], ['E', 3]]

 

3. 출력하기

추출한 알파벳 사용횟수를 for문을 통해 출력한다

 

---

• 코드(출력)

import sys, itertools

input = sys.stdin.readline

word_dic = {}

while True:
    word = input().rstrip()
    if word == '-':
        break
    word_dic[word] = 1


while True:
    puzzle =input().rstrip()
    if puzzle == '#':
        break
    puzzle_dic = {}
    alphabet_dic = {}
    puzzle = list(puzzle)
    for i in range(4,10):
        combination = list(itertools.combinations(puzzle, i))
        # 4 ~ 9개의 조합
        for comb in combination:
            permutation = list(itertools.permutations(comb,i))
            for perm in permutation:
                perm = ''.join(perm)
                if perm in word_dic:
                    if perm not in puzzle_dic:
                        puzzle_dic[perm] = 1
    for i in puzzle:
        if i not in puzzle_dic:
            alphabet_dic[i] = 0
    for dic_word in puzzle_dic:
        dic_word = set(dic_word)
        for k in dic_word:
            alphabet_dic[k] +=1
    
    print_list = []

    for i in alphabet_dic:
        print_list.append([i,alphabet_dic[i]])
    print_list.sort(key = lambda x : (x[1], x[0]))

    small = print_list[0][1]
    big = print_list[-1][1]
    min_list =[]
    max_list = []
    for i in print_list:
        if i[1] == small:
            print(i[0], end = '')
        else:
            break
    print(' '+ str(small), end = ' ')
    for i in print_list:
        if i[1] == big:
            print(i[0], end = '')
    print(' '+ str(big))

---

• 얻어갈 부분

1. 다른 사람의 풀이를 보니 각자 다른 방식으로 푼 것 같다. itertools의 comb와 perm의 문법이 생각이 나지 않아 문법을 조금 찾아보았다. 끝까지 풀어보려고 노력하고, 풀려서 기분이 좋다