[백준]_20920번 : 영단어 암기는 괴로워(파이썬)

20920번: 영단어 암기는 괴로워

짜증 나는 조건들이 심지어 우선순위를 이루고 있는 문제이다. 가장 먼저 떠올랐던 아이디어는 단어 길이가 M 이상인 단어들만 뽑아서 우선순위대로 [-(나온 횟수), -(길이), '단어']으로 구성된 리스트를 새로운 리스트([[...], [...], ...])에 전부 때려 박고 sort 해주면 간단히 해결될 문제라고 생각했다. 나온 횟수와 길이를 음수로 저장하는 이유는 sort를 하게 되면 맨 앞의 원서부터 오름차순으로 정렬되기 때문에 세 번째 조건인 사전순 조건에서 '단어' 자체는 의도와 부합하지만 나머지 둘은 음수로 저장하지 않으면 나온 횟수가 많은 것이 맨 뒤로 갈 것이고, 길이가 짧은 것이 앞으로 올 것이다.  하지만 이 접근법의 가장 큰 단점은 시간 복잡도에서 나온다. 아래의 코드를 살펴보면 나온 횟수를 갱신하는 데에 있어서 O(N^2)의 시간이 걸림을 알 수 있다.

시도 1(실패)

import sys
input = sys.stdin.readline

cnt, size = map(int, input().split())

ls = []
repo = []
for _ in range(cnt):
    word = input().strip()
    if len(word) >= size:
        if word not in repo:
            ls.append([0, -len(word), word])
            repo.append(word)
        else:
            for arr in ls:
                if arr[2] == word:
                    arr[0] -= 1
sort_ls = sorted((ls))
for el in sort_ls:
    print(el[2])

그래서 결국 전략을 바꿔야만 했는데.. 그것은 바로 해싱(사전)이다.

 

하지만 왜 해싱을 사용해야 될까? 해싱은 데이터 규모가 커질수록 다음과 같은 장점이 도드라진다.

1. key를 통해 특정 값에 접근할 때 상수 만큼의 시간 복잡도를 가진다.
2. 탐색 공간을 간소화 시켜준다.  

따라서 해싱을 사용해서 문제를 다시 풀어보자.

---

시도 2(파이썬)

import sys
input = sys.stdin.readline

cnt, size=map(int, input().split())

dic={}
for _ in range(cnt):
    word=input().strip()
    if len(word)>=size:
        if word not in dic:
            dic[word]=1
        else:
            if word in dic.keys():
                dic[word]+=1
sort_dic=dict(sorted(dic.items(), key=lambda w:(-w[1],-len(w[0]),w[0])))
for el in sort_dic:
    print(el)

<분석>

첫 번째 for문까지는 첫 번째 코드와 다를 바 없다. 하지만 대신 바로 그다음 줄의 lambda를 이용한 정렬 방법이 중요한 역할을 하였다. dic.items()는 dic의 키-값 쌍을 반환하는 메서드이고 정렬 키를 key로 지정하고 배열되는 방법을 lambda 함수를 사용하여 정한다. 이때 w[0] 은 word, w[1] 은 나온 횟수가 저장되어 있다.