[백준] 20920번 : 영단어 암기는 괴로워 – JAVA [자바]

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

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

 

---

• 문제

 

 

---

• 문제 풀이

백준 20920번 영단어 암기는 괴로워는 실버 3 난이도의 해시 및 정렬 문제이다. 

 

이 문제에서는 N개의 단어와 단어의 단어의 길이 기준인 M이 주어진다. 이때 단어의 길이가 M인 것들 중에서 다음과 같은 기준으로 정렬을 한 후 출력을 하면 된다.

 

1. 자주 나오는 단어일수록 앞에 배치한다.
2. 해당 단어의 길이가 길수록 앞에 배치한다.
3. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다

 

우선 '자주 나오는 단어'를 알기 위해서 HashMap을 사용한다. getOrDefault() 함수를 이용해서 각 단어가 나오는 빈도를 이 HashMap에 저장한다. 이건 다음과 같이 할 수 있다. HashMap의 키는 단어가 되고 값은 단어가 나온 빈도수가 된다.

 

map.put(s, map.getOrDefault(s, 0) + 1); // 이미 나온 단어인 경우 카운트 증가, 처음 나온 단어인 경우 1로 설정

 

그리고 이 단어들을 출력하는데 반복되는 단어들도 한 번만 출력하면 된다. 출력하기 위해서는 리스트를 사용해야 하므로 이 맵의 키들을 리스트로 변환하면 된다. 이건 다음과 같이 할 수 있다.

 

List<String> words = new ArrayList<>(map.keySet());

 

마지막으로 이제 가장 중요한 정렬만 하면 된다. 이 리스트를 정렬하기 위해서 직접 Comparator의 compare() 함수를 작성해 줘야 한다. 

 

우선, 단어의 빈도수대로 정렬해 줘야 한다. 단어의 빈도수는 맵의 값으로 저장되어 있다. 

 

만약에 빈도수가 같으면 단어의 길이를 내림차순으로 정렬해줘야 한다. 단어의 길이도 같으면 사전 순으로 정렬해줘야 한다. 사전순으로 정렬은 String 클래스에 있는 compareTo() 함수를 사용하면 된다. 완성된 정렬 로직은 다음과 같다.

 

Collections.sort(words, new Comparator<String>() {
    @Override
    public int compare(String o1, String o2) {
        // 자주 등장하는 단어 순서대로 정렬
        if (Integer.compare(map.get(o1), map.get(o2)) != 0) {
            return Integer.compare(map.get(o2), map.get(o1));
        }
        // 등장 횟수가 같으면 길이가 긴 단어가 먼저 오도록 정렬
        if (o1.length() != o2.length()) {
            return o2.length() - o1.length();
        }
        // 등장 횟수와 길이가 같으면 사전 순으로 정렬
        return o1.compareTo(o2);
    }
});

 

자세한 코드는 아래에 있는 코드를 참고하면 되겠다.

 

---

• 코드

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 입력: 단어의 개수 'n'과 최소 단어 길이 'm'을 읽음
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        // HashMap을 사용하여 길이가 'm' 이상인 단어들과 그 개수를 저장
        Map<String, Integer> map = new HashMap<>();
        
        // 'n'개의 단어를 읽으며, 길이가 'm' 이상인 단어의 등장 횟수를 세어 map에 저장
        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            if (s.length() < m) continue; // 길이가 'm' 미만인 단어는 무시
            map.put(s, map.getOrDefault(s, 0) + 1); // 이미 나온 단어인 경우 카운트 증가, 처음 나온 단어인 경우 1로 설정
        }
        
        // map에서 단어들을 가져와서 ArrayList에 저장
        List<String> words = new ArrayList<>(map.keySet());
        
        // words 리스트를 정렬
        Collections.sort(words, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                // 자주 등장하는 단어 순서대로 정렬
                if (Integer.compare(map.get(o1), map.get(o2)) != 0) {
                    return Integer.compare(map.get(o2), map.get(o1));
                }
                // 등장 횟수가 같으면 길이가 긴 단어가 먼저 오도록 정렬
                if (o1.length() != o2.length()) {
                    return o2.length() - o1.length();
                }
                // 등장 횟수와 길이가 같으면 사전 순으로 정렬
                return o1.compareTo(o2);
            }
        });
        
        // 정렬된 단어들을 출력
        StringBuilder sb = new StringBuilder();
        for (String str : words) {
            sb.append(str + "\n");
        }
        System.out.println(sb);
    }
}