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

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

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

 

 

[정답 코드]

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        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());
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < N; i++) {
            String word = br.readLine();
            if (word.length() >= M) { // 길이 M 이상만 저장
                map.put(word, map.getOrDefault(word, 0) + 1); // 같은 단어가 등록될경우 value를 하나씩 증가
            }
        }
        // map 의 value 기준 내림차순 정렬
        List<Map.Entry<String, Integer>> entryList = new LinkedList<>(map.entrySet());
        entryList.sort(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                int cmp = o2.getValue().compareTo(o1.getValue()); // value 기준 내림차순 정렬 0일경우 value가 같음
                if (cmp == 0) {
                    int lengthCompare = Integer.compare(o2.getKey().length(), o1.getKey().length()); // value가 같을 경우 value가 같은것 끼리 key의 길이를 내림차순 정렬
                    return lengthCompare == 0 ? o1.getKey().compareTo(o2.getKey()) : lengthCompare; // key의 길이가 같을경우(lengthCompare == 0일경우) 길이가 같은것은 사전순으로 정렬
                }
                return cmp;
            }
        });
        for (Map.Entry<String, Integer> entry : entryList) {
            bw.write(entry.getKey());
            bw.write("\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

 

[설명]

이 문제는 맵을 활용한 키와 밸류의 정렬, Comparator를 잘 활용해야하는 문제이다.

먼저 단어를 입력받을때 단어의 길이가 M 이상인 경우만 Map에 저장해준다. 같은 단어가 나올때 해당 단어의 갯수를 map으로 카운팅 해준다.

입력이 끝났다면 map의 Value를 기준으로 내림차순 정렬을 해준다. 그렇다면 

        // map 의 value 기준 내림차순 정렬
        List<Map.Entry<String, Integer>> entryList = new LinkedList<>(map.entrySet());
        entryList.sort(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                int cmp = o2.getValue().compareTo(o1.getValue()); // value 기준 내림차순 정렬 0일경우 value가 같음
                return cmp;
            }
        });

이런식으로 정렬을 해주면 된다.

 

하지만 문제에서 value 가 같을 경우에는 길이가 긴순으로 재 정렬을 해줘야한다고 되어있다. 그래서 약간 변형해

        // map 의 value 기준 내림차순 정렬
        List<Map.Entry<String, Integer>> entryList = new LinkedList<>(map.entrySet());
        entryList.sort(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                int cmp = o2.getValue().compareTo(o1.getValue()); // value 기준 내림차순 정렬 0일경우 value가 같음
                if (cmp == 0) {
                    int lengthCompare = Integer.compare(o2.getKey().length(), o1.getKey().length()); // value가 같을 경우 value가 같은것 끼리 key의 길이를 내림차순 정렬
                    return lengthCompare; 
                }
                return cmp;
            }
        });

 cmp 가 같을 경우에 조건문을 걸어 길이가 긴순으로 내림차순을 해준다.

 

하지만 문제에 또다른 조건이 있다. 길이마저 같을 경우에는 사전순으로 정렬을 해준다고 되어있다.

        // map 의 value 기준 내림차순 정렬
        List<Map.Entry<String, Integer>> entryList = new LinkedList<>(map.entrySet());
        entryList.sort(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                int cmp = o2.getValue().compareTo(o1.getValue()); // value 기준 내림차순 정렬 0일경우 value가 같음
                if (cmp == 0) {
                    int lengthCompare = Integer.compare(o2.getKey().length(), o1.getKey().length()); // value가 같을 경우 value가 같은것 끼리 key의 길이를 내림차순 정렬
                    return lengthCompare == 0 ? o1.getKey().compareTo(o2.getKey()) : lengthCompare; // key의 길이가 같을경우(lengthCompare == 0일경우) 길이가 같은것은 사전순으로 정렬
                }
                return cmp;
            }
        });

3항연산자를 사용해 lengthComapre가 같을경우에는 o1.getKey().compareTo(o2.getKey()) 로 비교해사전순으로 정렬해준다. 

그리고 마지막 출력을 할 때

        for (Map.Entry<String, Integer> entry : entryList) {
        	System.out.println(entry.getKey());
        }

이런식으로 출력을 할 경우 시간초과가 발생한다. 문제설명 맨 마지막에 설명을 보듯 BufferedWriter를 사용해주어야 시간초과가 발생하지 않는다.

 

BufferedWriter를 사용해 다시 코드를 작성한다면

        for (Map.Entry<String, Integer> entry : entryList) {
            bw.write(entry.getKey());
            bw.write("\n");
        }
        bw.flush();
        bw.close();
        br.close();

이런식으로 출력해 주어야 한다.