[백준][BOJ 20920] - 영단어 암기는 괴로워

문제

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

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

 

 

문제 접근

• 자주 나오는 단어일수록 앞에 배치된다.
• 단어의 길이가 길수록 앞에 배치한다.
• 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다
• 이때 길이 $M$미만의 단어는 무시한다.
• 먼저 빈도수를 잘 계산하기 위해 key-value로 $O(1)$ 시간에 접근이 가능한 map을 사용하였다. 이후 위의 우선순위에 맞도록 정렬을 수행하면 된다.
• 정렬의 우선순위가 3개가 있으므로 람다 구현이나 comparator 구현을 사용할 수 있다. 필자는 람다를 사용하여 구현하였다.

 

 

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {

  public static void main(String[] args) throws IOException {
    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> wordCount = new HashMap<>();

    for (int i = 0; i < N; i++){
      String data = br.readLine();

      if (data.length() < M){
        continue;
      }

      wordCount.put(data, wordCount.getOrDefault(data, 0) + 1);
    }

    List<String> keys = new ArrayList<>(wordCount.keySet());
    keys.sort((x, y) -> {
      if (wordCount.get(y) - wordCount.get(x) == 0){
        if (y.length() - x.length() == 0){
          return x.compareTo(y);
        } else{
          return y.length() - x.length();
        }
      } else{
        return wordCount.get(y) - wordCount.get(x);
      }
    });

    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    for (String key : keys){
      bw.write(key + "\n");
    }
    bw.flush();
  }
}

• 처음 System.out.println()으로 출력 시에 시간 초과가 떳다. 아마 출력 단도 최적화를 시켜야 통과하는 문제인 것 같다. 실제로 최적화 시킨 결과가 820ms로 추가 시간 없는 1초에는 좀 빡빡했을 것으로 추정된다.