[BOJ 20920] 영단어 암기는 괴로워

문제 요약

문제 요약
단어를 입력 받고
1 단어 빈도수
2 단어의 길이
3 사전 순
으로 단어장에 정렬하시오
입력
첫째 줄 : 단어 개수 (최대 10만), 외울 단어 길이 기준
둘째 줄 ~ N+1째 줄 : 외울 단어
출력
단어장의 맨 앞부터 출력

풀이

입력받은 단어들의 문자열과 빈도수를 저장하고 그 저장한 것을 3가지 기준으로 출력하면 된다.

어디에 저장해야 할까?

파이썬의 자료형 및 연산자의 시간 복잡도를 확인하면 set과 dictionary의 요소 추가, 탐색의 시간복잡도가 O(1)로 매우 빠름을 확인할 수 있다.
우리는 단어의 빈도수가 필요하므로 dictionary를 사용할 것이다.

Dictionary 자료형에 어떤 식으로 넣어야 할까?

간단하게 N번 반복하는 반복문 안에서 word를 받고
1. M보다 길이가 짧으면 continue
2. M보다 길이가 길면
2-1. 이미 dictionary에 있으면 빈도수를 1 더한다

voca[word] += 1

2-2. dictionary에 없는 새로운 단어라면 빈도수를 1로 잡고 추가한다

voca[word] = 1

저장한 뒤에 다중 조건으로 출력하려면 어떻게 해야할까?

다중 조건으로 출력하는 방법으로는 lambda식을 사용하는 방법이 있다.

lambda식으로 다중 조건 출력하는 방법

sorted([정렬할 데이터], key = lambda x : ([정렬기준1], [정렬기준2], ...))

예를 들어 dictionary를 {"word", 3} 이런식으로 저장한다고 하면
빈도수를 기준으로 내림차순으로 출력하려면 정렬기준을 -x[1]으로 놓으면 된다. (-는 내림차순을 의미한다)

신경써야 할 부분

입력수가 10만이니 input할 때 sys.stdin.readline을 사용한다.
word를 매번 받을 때마다 개행문자도 같이 입력이 되기 때문에 len()함수를 쓸 때 원래 글자 수보다 +1이 될 수 있다.
그러므로 rstrip()을 통해 개행문자를 거르면 된다.

결과 코드

import sys
input = sys.stdin.readline

N, M = map(int,input().split())
voca = {}

for _ in range(N):
    word = input().rstrip()

    if len(word) < M: 
        continue
    else:
        if word in voca:
            voca[word] += 1
        else:
            voca[word] = 1

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