백준 영단어 암기는 괴로워 (20920번) 파이썬

백준 영단어 암기는 괴로워 20920 파이썬

문제

• 단어 N개가 주어진다.
• 길이가 M 이상인 단어만 암기 대상이다.
• 단어의 정렬 기준은 다음과 같다:
1. 많이 등장한 단어가 먼저
2. 단어 길이가 길수록 먼저
3. 사전순으로 앞선 단어가 먼저
• 출력은 정렬된 단어들을 한 줄씩 출력한다.

---

테스트케이스

입력 1

7 4
apple
ant
sand
apple
append
sand
sand

출력 1

sand
apple
append

입력 2

12 5
appearance
append
attendance
swim
swift
swift
swift
mouse
wallet
mouse
ice
age

출력 2

swift
mouse
appearance
attendance
append
wallet

---

문제작동원리

1. 단어를 입력받으면서 길이가 M 이상인지 확인한다.
2. 단어 빈도를 세기 위해 **딕셔너리(dictionary)**를 사용한다.
3. 모든 단어를 리스트에 옮겨 담은 뒤 `sort()`로 정렬한다.
4. 정렬 기준:
   • 등장 횟수 N (내림차순)
   • 단어 길이 len (내림차순)
   • 사전순 (오름차순)

---

아이디어

• 파이썬의 **딕셔너리**를 활용해 단어 빈도를 효율적으로 집계한다.
• 이후 **커스텀 정렬**을 위해 `Word` 클래스를 정의하고, `__lt__` 메소드를 오버라이딩하여 문제의 정렬 기준을 구현한다.
• 마지막으로 정렬된 리스트를 순회하며 출력한다.
• 이렇게 하면 복잡한 구현 없이 문제를 효율적으로 해결할 수 있다.

---

전체코드

import sys
input = sys.stdin.readline

class Word:
    def __init__(self, arr, N):
        self.arr = arr
        self.N = N
        self.lenArr = len(arr)
    
    def __lt__(self, word):
        if self.N != word.N:
            return self.N > word.N
        if self.lenArr != word.lenArr:
            return self.lenArr > word.lenArr
        return self.arr < word.arr

    def __str__(self):
        return f'{self.arr}'

N, M = map(int, input().split())
arr = dict()
for i in range(N):
    temp = input().strip()
    if len(temp) < M:
        continue
    if temp in arr:
        arr[temp] += 1
    else:
        arr[temp] = 1

st = []
for key, val in arr.items():
    st.append(Word(key, val))

st.sort()

for i in range(len(st)):
    print(st[i])

---

결론

• 파이썬의 **딕셔너리**를 사용해 단어 빈도 집계를 \(O(N)\)으로 처리할 수 있습니다.
• 클래스를 정의하고 **`__lt__` (less than) 메소드를 오버라이딩**하여 여러 정렬 기준을 한 번에 적용할 수 있습니다.
• 이를 통해 BOJ 20920번 문제를 시간 초과 없이 효율적으로 해결할 수 있습니다.