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

이 글은 읽는데 약 5분이 걸립니다.

※개인 공부 목적의 정리글입니다.
이 글의 내용이 최선의 해답은 아닐 수 있습니다.

문제

화은이는 이번 영어 시험에서 틀린 문제를 바탕으로 영어 단어 암기를 하려고 한다. 그 과정에서 효율적으로 영어 단어를 외우기 위해 영어 단어장을 만들려 하고 있다. 화은이가 만들고자 하는 단어장의 단어 순서는 다음과 같은 우선순위를 차례로 적용하여 만들어진다.

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

 \(M\)보다 짧은 길이의 단어의 경우 읽는 것만으로도 외울 수 있기 때문에 길이가 \(M\)이상인 단어들만 외운다고 한다. 화은이가 괴로운 영단어 암기를 효율적으로 할 수 있도록 단어장을 만들어 주자.

입력

첫째 줄에는 영어 지문에 나오는 단어의 개수 \(N\)과 외울 단어의 길이 기준이 되는 \(M\)이 공백으로 구분되어 주어진다. \((1 \leq N \leq 100\,000, \;1 \leq M \leq 10)\)

둘째 줄부터 \(N+1\)번째 줄까지 외울 단어를 입력받는다. 이때의 입력은 알파벳 소문자로만 주어지며 단어의 길이는 \(10\)을 넘지 않는다.

단어장에 단어가 반드시 \(1\)개 이상 존재하는 입력만 주어진다.

출력

화은이의 단어장에 들어 있는 단어를 단어장의 앞에 위치한 단어부터 한 줄에 한 단어씩 순서대로 출력한다.

풀이

단순히 정렬해서 출력하는 것이 아니라, 세 개의 조건을 모두 고려하면서 정렬을 하여야한다.

일단 단어들을 입력 받으면서 길이가 M 미만인 것들은 무시한다. 또한 각 단어들의 출현 횟수를 카운팅 하는데, HashMap을 사용할 것이다. <단어, 횟수> 형태로 만들것이다.

이제 단어 출현 횟수가 저장된 HashMap의 키들을 배열로 바꾼다. 어차피 정렬해야 하므로 순서는 상관없다. HashMap의 ketSet()메소드를 이용하여 키들만(즉 단어들만) 가져와 배열로 만든다.

이후 Arrays.sort()를 이용하되 커스텀 정렬을 위해서 직접 Comparator를 구현해줘야하며, 이것을 제대로 구현하는 것이 문제의 핵심 되겠다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();

String[] inputs = br.readLine().split(" ");
int N = Integer.parseInt(inputs[0]);
int M = Integer.parseInt(inputs[1]);

HashMap<String, Integer> freq = new HashMap<>();  // <단어, 출현횟수> 저장용 해시맵

for(int i=0; i<N; i++){
    String word = br.readLine();
    if(word.length() < M) continue;  // 최소길이 미만인 단어는 pass

    freq.put(word, freq.getOrDefault(word, 0) + 1);  // 단어 출현횟수 카운팅
}

String[] word_list = freq.keySet().toArray(new String[freq.size()]);  // 해시맵의 keySet에서 단어들의 배열을 만든다. 순서는 상관 X

Arrays.sort(word_list, (a, b) -> {  // 위에서 만든 단어 배열을 실제로 정렬한다.
    int comp_freq = freq.get(b) - freq.get(a);  // 먼저 빈도수를 기준으로 비교
    if(comp_freq != 0){
        return comp_freq;
    }else{  // 빈도수가 같으면
        int comp_len = b.length() - a.length();  // 길이로 비교
        if(comp_len != 0){
            return comp_len;
        }else{  // 길이도 같으면
            int comp_dict = a.compareTo(b);  // 사전순으로 비교
            return comp_dict;  // 사전순에서 0이 나오려면 단어가 완전히 같아야되는데 중복이 없으므로 그냥 리턴해도 무방
        }
    }
});

for(String s : word_list){  // 정렬된 단어들 출력
    sb.append(s).append("\n");
}

System.out.println(sb.toString());
br.close();

댓글