[백준 BOJ/Silver III] 20920번 : 영단어 암기는 괴로워

 

 

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

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

 

package BOJ20920;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.Map.Entry;

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> word = new HashMap<>();

        int index = 0;
        while(index < N) {
            st = new StringTokenizer(br.readLine());
            String s = st.nextToken();
            if(s.length() >= M) {
                word.put(s, word.getOrDefault(s, 0) + 1); // key : 단어, value : 몇 번 나오
            }
            index++;
        }

        List<Map.Entry<String, Integer>> entryList = new ArrayList<>(word.entrySet());
        Collections.sort(entryList, (o1, o2) -> {

            if(o2.getValue() - o1.getValue() != 0) {
                return o2.getValue() - o1.getValue(); // value 크면(자주 나오는 단어) 앞으로

            } else if (o2.getKey().length() - o1.getKey().length() != 0) {
                return o2.getKey().length() - o1.getKey().length(); // key 길이(=단어 길이) 길수록 앞으로

            } else {
                return o1.getKey().compareTo(o2.getKey()); // 알파벳 순으로
            }

        });

//        for(int i = 0; i<entryList.size(); i++) {
//            System.out.println(entryList.get(i).getKey());
//        }

        StringBuilder  stringBuilder = new StringBuilder();
        for(int i = 0; i<entryList.size(); i++) {
            stringBuilder.append(entryList.get(i).getKey()).append("\n");
        }
        System.out.println(stringBuilder.toString());

    }

}

 

통과하고나서 굉장히 얼떨떨했다

 

정렬하는 방법은 맞는거 같은데 시간초과가 나와서 이것저것 조금씩 바꿔보고 반복했다 근데도 계속 시간초과만 떠서 어떤걸 더 해봐야할지 고민이 많았다 마지막으로 map에서 key만 가져와서 배열로 만들고 비교할까? 하는 생각이 들어서 고쳐보려다가 잠시 환기 차 풀었던 문제에서 썼던 BufferedReader를 써서 가볍게 고쳐본건데,,, 통과한거다😮😮😮😮😮😮😮😮

약간 황당할 정도였다 그렇게 고민하며 고치고고칠때는 계속 시간초과가 나더니,,, 

앞으로 백준 문제 입력은 무조건 BufferedReader 를 써야겠다 아주 간단한 입력 제외하고!

시간초과로 인해 헤맸던 기록은 뒤에 남기고 우선 답을 냈던 과정을 쓰자면

 

.

.

        int index = 0;
        while(index < N) {
            st = new StringTokenizer(br.readLine());
            String s = st.nextToken();
            if(s.length() >= M) {
                word.put(s, word.getOrDefault(s, 0) + 1); // key : 단어, value : 몇 번 나오
            }
            index++;
        }

 

한줄씩 문자를 입력받고 길이가 M 이상일떄만 HashMap에 넣고 나오는 횟수를 더해줬다

이는 자주 나오는 단어가 우선순위 기준에 들어가기 때문에 꼭 필요한 과정이다

key는 단어고 value는 그 단어가 나온 횟수

 

 

이제는 우선순위 조건엔 맞게 정렬해주면 되는데

	List<Map.Entry<String, Integer>> entryList = new ArrayList<>(word.entrySet());
        Collections.sort(entryList, (o1, o2) -> {

            if(o2.getValue() - o1.getValue() != 0) {
                return o2.getValue() - o1.getValue(); // value 크면(자주 나오는 단어) 앞으로

 

먼저, 정렬을 해주기 위해 HashMap을 ArrayList로 바꿔주었다

자주 나오는 단어가 앞으로 와야하기때문에 value 기준으로 내림차순 정렬!

 

 

	else if (o2.getKey().length() - o1.getKey().length() != 0) {
                return o2.getKey().length() - o1.getKey().length(); // key 길이(=단어 길이) 길수록 앞으로

            }

 

다음 우선순위 조건으로

단어의 길이가 길수록 앞으로 오기 때문에 key의 길이 기준으로 내림차순 정렬!

 

 

	else {
                return o1.getKey().compareTo(o2.getKey()); // 알파벳 순으로
            }

 

다음 우선순위 조건으로 알파벳 사전순으로 정렬!

이렇게까지 하면 정렬이 완료되고 출력해주면 끝!!!!!!

 

 

---

 

시간초과 났던 기록✨

 

 

아래가 가장 처음 제출했던 코드이다

import java.util.*;
import java.util.Map.Entry;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(); // 단어 개수
        int M = sc.nextInt(); // 단어 길이 기준
        Map<String, Integer> word = new HashMap<>();


        int index = 0;
        while(index < N) {
            String s = sc.next();
            if(s.length() >= M) {
                word.put(s, word.getOrDefault(s, 0) + 1); // key : 단어, value : 몇 번 나오
            }
            index++;
        }

        List<Map.Entry<String, Integer>> entryList = new LinkedList<Map.Entry<String,Integer>>(word.entrySet());
        entryList.sort(new Comparator<Map.Entry<String, Integer>>() {

            @Override
            public int compare(Entry<String, Integer> o1, Entry<String, Integer> o2) {
                if(o2.getValue() - o1.getValue() != 0) {
                    return o2.getValue() - o1.getValue(); // value 크면(자주 나오는 단어) 앞으로

                } else if (o2.getKey().length() - o1.getKey().length() != 0) {
                    return o2.getKey().length() - o1.getKey().length(); // key 길이(=단어 길이) 길수록 앞으로

                } else {
                    return o1.getKey().compareTo(o2.getKey()); // 알파벳 순으로
                }
            }
        });

        //System.out.println(entryList);
        for(int i = 0; i<entryList.size(); i++) {
            System.out.println(entryList.get(i).getKey());
        }

    }

}

 

1. LinkedList 보다 ArrayList가 좀 더 빠르게 확인할 수 있다고 하여 변경

List<Map.Entry<String, Integer>> entryList = new ArrayList<>(word.entrySet());

 

2. System.out.println 보다 출력 속도가 빠른 StringBilder 이용하여 변경

        StringBuilder  stringBuilder = new StringBuilder();
        for(int i = 0; i<entryList.size(); i++) {
            stringBuilder.append(entryList.get(i).getKey()).append("\n");
        }

        System.out.println(stringBuilder.toString());

 

3. 람다식으로 변경

 Collections.sort(entryList, (o1, o2) -> {

 

이외에도 Comparator 를 따로 빼서 정의하고 sort 에 넣어주기 등 시간초과를 잡기 위한 정말 많은 시도를 했었다

 

요즘 코테를 풀면서 느끼는건 효율성 있게, 시간초과 안나게 작성하는게 정말 어렵다는거다 더 좋은 방향으로 생각할 수 있도록 더 많은 문제를 풀고 더 노력해야겠다