[파이썬/python] 백준 20920 - 영단어 암기는 괴로워

문제

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

---

문제 설명

1. N개의 단어를 입력받는다.
2. N개의 단어 중 길이가 M이상인 단어들만 외워야 한다.
3. 단어들을 외우는 순서에는 우선순위가 존재한다.
   1. 자주 나오는 단어일수록 앞에 배치한다.
   2. 해당 단어의 길이가 길수록 앞에 배치한다.
   3. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다. 

 

---

풀이

1. N개의 단어를 입력받을 때 길이가 M이상인 단어들만 갯수를 Count한다.
2. 암기 우선순위에 맞게 정렬한다.

---

코드

import sys

dic = dict()
n,m = map(int,input().split())

for i in range(n):
    word = input().strip()
    if len(word) < m:
        continue
    if word not in dic:
        dic[word] = 1
    else:
        dic[word]+=1
dic = list(dic.items())

dic.sort(key = lambda x: (-x[1] ,-len(x[0]), x[0]))

for i in dic:
    print(i[0])

---

시간복잡도

• N개의 단어를 딕셔너리에 입력받을 때 $O(N)$
• 딕셔너리의 원소를 정렬할 때 $O(NlogN)$
• 최악일 경우 $N = 10^5$이므로 약 $O(10^5 * 20) = O(10^6)$의 시간복잡도를 가진다.