문제 출처

https://www.acmicpc.net/problem/20920
단계별로 풀어보기 > 심화 2 > 영단어 암기는 괴로워

문제 설명

단어의 갯수 N, 단어의 길이 M이 주어지고,
이 후 단어의 갯수만큼 단어들이 한줄씩 주어진다.

다음과 같은 순서로 단어를 정렬하라
1. 자주 나오는 단어일수록 앞에 배치한다.
2. 해당 단어의 길이가 길수록 앞에 배치한다.
3. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다.

접근 방법

1. Comparator를 이용한 방법

단어가 언급된 횟수를 기록하기 위해 HashMap을 통해 해당 횟수를 저장한다.
Comparator 객체 comp를 생성한다. 이 때, 조건은 횟수가 저장되어있는 HashMap에서 꺼내와 횟수를 비교하고, 해당 단어의 길이를 비교한 후, 사전순으로 정렬한다.

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

public class 영단어_암기는_괴로워 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        HashMap<String,Integer> hm = new HashMap();

        for(int i =0; i<N; i++){
            String str = br.readLine();
            if(str.length() < M){
                continue;
            }

            hm.put(str,hm.getOrDefault(str,0)+1);
        }


        List<String> result = new ArrayList<>(hm.keySet());
        Comparator<String> comp = Comparator.comparingInt((String word) -> hm.get(word))
                        .thenComparing((String word) -> word.length()).reversed()
                        .thenComparing(Comparator.naturalOrder());

        result.sort(comp);

        StringBuilder sb = new StringBuilder();

        for (String s : result) {
            sb.append(s).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

}

2.compareTo 이용 방법

import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {

//                1. 자주 나오는 단어일수록 앞에 배치한다.
//                2. 해당 단어의 길이가 길수록 앞에 배치한다.
//                3. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        HashMap<String, Integer> hm = new HashMap<>();

        for(int i = 0; i<N; i++){
            String str = br.readLine();
            if(str.length() < M) continue;
            hm.put(str, hm.getOrDefault(str, 0) + 1);
        }

        ArrayList<String> result = new ArrayList<>(hm.keySet());

        result.sort((o1,o2) -> {
            if(!hm.get(o1).equals(hm.get(o2))){
                return hm.get(o2) - hm.get(o1);
            } else if (o1.length() != o2.length()){
                return o2.length() - o1.length();
            } else{
                return o1.compareTo(o2);
            }
        });

        StringBuilder sb = new StringBuilder();

        for (String s : result) {
            sb.append(s).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();

    }
}

Review
1. Comparator

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

public class 영단어_암기는_괴로워_review {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        HashMap<String,Integer> hm = new HashMap<>();

        for(int i = 0; i<N; i++){
            String line = br.readLine();
            if(line.length() < M) continue;

            hm.put(line, hm.getOrDefault(line,0) +1);
        }

        List<String> list = new ArrayList<>(hm.keySet());

        Comparator<String> comp = Comparator
                .comparingInt((String word) ->hm.get(word))
                .thenComparing((String word) -> word.length()).reversed()
                .thenComparing(Comparator.naturalOrder());

        list.sort(comp);

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

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();

    }

}

2. Comparable

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

public class 영단어_암기는_괴로워_comparable_review {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        HashMap<String,Integer> hm = new HashMap<>();

        for(int i = 0; i<N; i++){
            String line = br.readLine();
            if(line.length() < M) continue;

            hm.put(line, hm.getOrDefault(line,0) +1);
        }

        List<String> list = new ArrayList<>(hm.keySet());

        list.sort((o1, o2) ->{
            if (!hm.get(o1).equals(hm.get(o2))) {
                return hm.get(o2) - hm.get(o1);
            } else if (o1.length() != o2.length()){
                return o2.length() - o1.length();
            }else{
                return o1.compareTo(o2);
            }
                }
        );

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

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();

    }

}

알게된 점

항상 정렬문제는 Comparator나 Comparable의 사용 방법 때문에 헷깔리는 것 같다.
확실하게 사용법을 익혀서 객체 정렬할 때, 사용해야겠다.

Review
배열을 이용해서 풀어보려고 했으나, 배열을 사용하면 시간 초과가 발생했다.

문제푼 흔적