코딩테스트/BOJ

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

5월._. 2023. 3. 22.
728x90

1. 문제

 

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

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

www.acmicpc.net

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

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

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


2. 풀이

횟수 기록용 map과 나중에 정렬을 위한 list로 나눴다. 

1.  단어를 입력받을 때, 만약 길이가 M미만이라면 넘어간다.

2.  map에 key가 있는지 확인한 후 없다면 list에 추가한다.

3.  map.put은 삽입과 갱신 둘 다 할 수 있는 메서드이므로 map.getOrDefault를 이용해 key가 있든 없든 알아서 작동하도록 했다.

4.  정렬은 문제에서 제시한 순서대로 진행한다.(자주 나올수록, 단어 길이 길수록, 알파벳 사전 순)

5.  정렬이 끝난 list를 하나씩 SB에 모아서 한 번에 출력한다.

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

public class BOJ_20920_영단어암기는괴로워 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int N = Integer.parseInt(st.nextToken());
      int M = Integer.parseInt(st.nextToken());

      Map<String, Integer> map = new HashMap<>();
      List<String> list = new ArrayList<>();

      String word;
      for (int i = 0; i < N; i++) {
         word = in.readLine();
         if (word.length() < M) continue;
         if (!map.containsKey(word)) {
            list.add(word);
         }
         map.put(word,map.getOrDefault(word,0)+1);
      }

      //자주 나올수록, 단어 길이 길수록, 알파벳 사전순으로 앞에 배치
      Collections.sort(list, (o1, o2) -> {
         if (map.getOrDefault(o1, 0) != map.getOrDefault(o2, 0)) {
            return map.getOrDefault(o2, 0) - map.getOrDefault(o1, 0);
         } else if (o1.length() != o2.length()) {
            return o2.length() - o1.length();
         } else {
            return o1.compareTo(o2);
         }
      });

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

      System.out.print(sb);
   }
}

3. 결과

pq 사용해서 풀었다가 시간초과 났다. 생각해보니 굳이 실시간으로 입력받을 때마다 정렬할 필요가 없는 문제라 list로 수정해서 맞았다.

갑자기 map.keySet으로 list를 한번에 만들면 되지 않을까? 하는 생각이 들어서 시도해봤는데 시간이 더 걸렸다. 음.. 이건 왜 이런지 알아봐야할 것 같다(나중에^_ㅜ).

본문 코드는 두번째 코드다!

'코딩테스트 > BOJ' 카테고리의 다른 글

[BOJ] 1253 좋다 - JAVA  (0) 2023.03.24
[BOJ] 1644 소수의 연속합 - JAVA  (0) 2023.03.23
[BOJ] 20922 겹치는 건 싫어 - JAVA  (0) 2023.03.21
[BOJ] 1543 문서 검색 - JAVA  (0) 2023.03.20
[BOJ] 1940 주몽 - JAVA  (0) 2023.03.18

댓글