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

난이도: ★★☆☆☆ • solved on: 2026-01-17

---

문제 요약

• 문제 유형: 문자열 처리, 정렬, 해시

• 요구사항:

  • 길이가 M 이상인 단어만 대상으로 한다

  • 단어를 다음 기준으로 정렬해야 한다

    1. 자주 나오는 단어일수록 앞에 온다
    2. 길이가 긴 단어일수록 앞에 온다
    3. 사전 순으로 앞서는 단어일수록 앞에 온다

---

사용 개념

1. 자료구조

   • HashMap<String, EnglishWord> : 단어별 등장 횟수 저장
   • List<EnglishWord> : 정렬을 위한 리스트

2. 알고리즘/기법

   • 해시를 이용한 빈도 카운팅
   • Comparable 구현을 통한 커스텀 정렬
   • 스트림 정렬 (stream().sorted())

3. 핵심 키워드

   • 빈도 기반 정렬 (frequency sort)
   • 다중 조건 정렬 (multi-level sort)

---

풀이 아이디어 및 코드

방법 1 : Custom Comparator

1. 문제 분해

• 단어를 입력받으며 길이가 M 미만이면 무시한다
• HashMap에 단어를 key로, 등장 정보를 value로 저장한다
• 이미 등장한 단어면 횟수만 증가시킨다

2. 정렬 전략

   • EnglishWord 클래스에서 Comparable을 구현한다

   • 정렬 기준

     1. 등장 횟수 오름차순
     2. 단어 길이 오름차순
     3. 사전 역순

   • Collections.reverseOrder()로 전체 정렬 결과를 뒤집는다

3. 출력

   • 정렬된 리스트를 순회하며 단어만 출력한다

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] cmds = br.readLine().split(" ");
        int n = Integer.parseInt(cmds[0]);
        int m = Integer.parseInt(cmds[1]);

        HashMap<String, EnglishWord> map = new HashMap<>();

        for(int i = 0; i < n; i++) {
            String word = br.readLine();
            if(word.length() < m) continue;

            if(!map.containsKey(word)) {
                map.put(word, new EnglishWord(word));
            } else {
                map.get(word).updateCnt();
            }
        }

        List<EnglishWord> list = map.values().stream()
                .sorted(Collections.reverseOrder())
                .toList();

        StringBuilder sb = new StringBuilder();
        for(EnglishWord word : list) {
            sb.append(word.word).append("\n");
        }

        System.out.println(sb);
    }

    static class EnglishWord implements Comparable<EnglishWord> {
        String word;
        int cnt;

        public EnglishWord(String word) {
            this.word = word;
            this.cnt = 1;
        }

        @Override
        public int compareTo(EnglishWord anotherWord){
            if(cnt - anotherWord.cnt != 0){
                return cnt - anotherWord.cnt;
            }
            if(word.length() - anotherWord.word.length() != 0){
                return word.length() - anotherWord.word.length();
            }
            return -1 * word.compareTo(anotherWord.word);
        }

        public void updateCnt(){
            cnt++;
        }
    }
}

---

방법 2 : Custom Class 없이 Comparator 활용

1. 개선 포인트

• 별도의 클래스를 만들지 않는다
• 정렬 기준을 Comparator 체이닝으로 한눈에 드러낸다
• reverseOrder()를 쓰지 않아도 된다

2. 정렬 기준 명시

   • 빈도 내림차순
   • 길이 내림차순
   • 사전 오름차순

import java.io.*;
import java.util.*;
import java.util.stream.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        Map<String, Integer> map = new HashMap<>();

        for(int i = 0; i < n; i++) {
            String word = br.readLine();
            if(word.length() < m) continue;
            map.put(word, map.getOrDefault(word, 0) + 1);
        }

        List<String> result = map.keySet().stream()
                .sorted((a, b) -> {
                    if(map.get(a) != map.get(b))
                        return map.get(b) - map.get(a);
                    if(a.length() != b.length())
                        return b.length() - a.length();
                    return a.compareTo(b);
                })
                .toList();

        StringBuilder sb = new StringBuilder();
        for(String w : result) sb.append(w).append("\n");
        System.out.print(sb);
    }
}

---

시간·공간 복잡도

방법 1

• 시간 복잡도: O(N log N)
• 공간 복잡도: O(N)

방법 2

• 시간 복잡도: O(N log N)
• 공간 복잡도: O(N)

---

어려웠던 점

• HashMap의 value 객체들을 기준에 맞게 정렬하려다 보니 클래스를 만들고 Comparable을 구현하는 과정이 길어졌다

---

배운 점 및 팁

• 정렬 기준이 명확한 문제는 Comparator가 가독성이 더 좋다
• Comparable + reverseOrder() 방식은 기준이 많아질수록 직관성이 떨어질 수 있다
• 단순 빈도 문제는 Map<String, Integer> 구조만으로도 충분하다

---

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/20920
• 참고 블로그/깃허브: 없음

---

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • 백준 - 1302반 베스트셀러
  • 백준 - 11536번 줄 세우기

• 확장 문제 (GPT 추천):

  • 백준 - 1181번 단어 정렬