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

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

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

 

💡문제 분석 요약

영단어를 입력받고, 자주 입력받은 횟수, 단어 길이, 사전순으로 정렬하여 출력한다.

 

💡알고리즘 설계

1. 해시를 이용하여 key에 단어를, value에 단어가 입력된 횟수를 하나씩 늘리면서 저장한다.

- hash에 입력받은 단어가 있는지 체크하고, 없으면 hash[word]=1, 있으면 hash[word]+=1로 갯수를 추가한다.

2. 해시의 key를 value가 높은 순, len(value)가 긴 순, 사전 순으로 람다식을 이용해 정렬한다.

- 해시의 item을 정렬하려면 hash.items()로 아이템을 선택해야한다.

- 람다식을 이용해 정렬할때, -x로 x 앞에 -를 붙이면 기존 기준의 역순으로 정렬한다. 여러 조건을 우선순위에 따라 차례대로 적으면 된다.

 

💡코드

from collections import deque
import sys
input = sys.stdin.readline
import sys
input = sys.stdin.readline

N, M=map(int, input().split())
hash={}
result=[]

for _ in range(N):
    word=input().rstrip()
    if len(word)>=M:
        if word in hash:
            hash[word]+=1
        else:
            hash[word]=1

result=sorted(hash.items(), key=lambda x: (-x[1], -len(x[0]), x[0]))
for i in result:
    print(i[0])

💡시간복잡도

정렬: O(nlogn)