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

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

단어가 주어지고, 각 조건을 만족하는 순서대로 출력을 해야한다.

처음엔 실버 3문제라 쉽게 풀릴거라고 생각했는데 생각보다 쉽지 않았다.

이 문제는 java의 유용한 라이브러리를 많이 써야하는 문제였다.

 

해설

for(int i =0;i<n;i++){
  arr[i] = br.readLine();
  if(arr[i].length()>=m) map.put(arr[i],map.getOrDefault(arr[i],0)+1);
}

단어를 입력받을 때, 단어가 조건의 길이를 넘기면 해시맵에 해당 단어를 넣는다.

이때 value값은 해당 단어가 나온 횟수이다. map에 이미 단어가 존재한다면 그 value를 꺼내서 1을 더해 다시 넣어주고, 아니면 1을 넣어준다

나는 보통 이럴 때 contains 함수를 사용했는데 getOrDefault 함수를 쓰니 더 편리하다

 

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

그 다음 리스트에 map에 들어가있는 key들을 넣어준다. map.keySet()를 하면 map 내부의 key값들이 리스트로 반환된다

 

이때 중요한 점이 있다.

나는 LinkedList를 주로 사용해서 이번에도 그렇게 했는데 시간초과가 났다. ArrayList를 써야 성능이 더 좋다고 한다

앞으로는 웬만하면 ArrayList를 사용해야겠다.

아 그런데 큐는 LinkedList 사용해야한다고 한다!

 

Collections.sort(list,new Comparator<String>(){
  @Override
  public int compare(String o1,String o2){
    if(Integer.compare(map.get(o1), map.get(o2))!=0){
      return map.get(o2)-map.get(o1);
    }
    if(o1.length() != o2.length()){
      return o2.length() - o1.length();
    }
    return o1.compareTo(o2);
  }
});

그 다음 이 문제의 핵심인 comparator이다. 

이건 써도써도 헷갈린다.

Integer.compare 함수를 쓰면 같으면 0, 앞이 크면 1, 뒤가 크면 -1을 반환한다고 한다.

그리고 compareTo를 사용하면 String을 사전순으로 정렬할 수 있다. 우리는 사전순으로 오름차순으로 정렬하고자 하니까 o1.compareTo(o2)로 작성하였다.

 

StringBuilder sb = new StringBuilder();

for(int i =0 ;i<list.size();i++){
  sb.append(list.get(i)+"\n");
}

System.out.println(sb);

 

또한 결과값을 출력할 때 그냥 출력하면 시간초과가 난다.

따라서 java에서 출력을 빠르게 하도록 지원하는 StringBuilder을 사용해야한다

 

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

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());
    HashMap<String, Integer> map = new HashMap<>();

    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());

    String[] arr = new String[n];

    for(int i =0;i<n;i++){
      arr[i] = br.readLine();
      if(arr[i].length()>=m) map.put(arr[i],map.getOrDefault(arr[i],0)+1);
    }

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

    Collections.sort(list,new Comparator<String>(){
      @Override
      public int compare(String o1,String o2){
        if(Integer.compare(map.get(o1), map.get(o2))!=0){
          return 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(int i =0 ;i<list.size();i++){
      sb.append(list.get(i)+"\n");
    }

    System.out.println(sb);


  }
}

 

전체 코드이다.

여러모로 까다롭지만 중요한 문제였다.