[백준/Python] 20920 : 영단어 암기는 괴로워

 

 

조건에 따라 단어들을 각 단어의 출현 빈도, 길이, 그리고 사전순으로 정렬한 뒤 결과를 출력하는 문제이다.

 

1. Counter를 이용하여 단어의 출현 빈도 계산 (counter는 각 단어가 몇 번 등장했는지 계산)

2. 길이가 M 이상인 단어들만 필터링

3. 출현 빈도, 단어의 길이, 사전순으로 단어를 정렬 -> sorted 함수에 key 인자로 정렬 기준 제공 

(출현 빈도를 내림차순으로 : -word_count[word] / 길이를 내림차순으로 : -len(word) / 사전순 : word)

4. 정렬된 단어를 한 줄에 하나씩 출력

 

처음엔 위와 같은 순서로 작성하였는데, 1초로 제한되어 있어서 백준에 제출했을 때 시간 초과 오류가 발생하였다. 

 

따라서 다음과 같이 수정하여 성공

 

from collections import Counter
import sys

def make_vocabulary(N, M, words):
    # 단어의 출현 빈도 계산
    word_count = Counter(words)
    
    # 길이가 M 이상인 단어만 필터링하고 정렬 준비
    filtered_words = [word for word in word_count if len(word) >= M]
    
    # 정렬 조건: (-출현 빈도, -길이, 사전순)
    filtered_words.sort(key=lambda word: (-word_count[word], -len(word), word))
    
    sys.stdout.write("\n".join(filtered_words) + "\n")

N, M = map(int, input().split())
words = [sys.stdin.readline().strip() for _ in range(N)]
make_vocabulary(N, M, words)

 

단어의 수가 최대 100,000개이기 때문에, counter와 sorted를 적절히 사용하여 시간을 줄이는 것이 중요

- 입력을 받으면서 Counter를 사용해 단어의 빈도를 계산

- 조건에 따라 Counter를 직접 처리해 불필요한 중복을 제거

- 정렬 작업을 한 번만 수행하여 성능을 개선

- sys.stdin.readline과 sys.sdout.write를 사용하여 입출력 성능을 최적화