Algorithm, Problem Solving/백준(boj)

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

태오님 2023. 10. 26.

목차

    문제 정보

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

     

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

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

    www.acmicpc.net

    난이도 : S3

    유형 : 정렬, 해쉬


    문제 풀이

    문자들을 우선순위에 따라 정렬하는 것이 이 문제의 핵심이다. 

     

    일단 해쉬맵을 이용하여 문자열을 처리해야한다. 

    해쉬맵의 getOrDefault() 메소드를 활용하여 개수를 처리

     

    해쉬맵의 데이터를 리스트로 전달하고

    구현한 정렬로직을 통하여 리스트를 정렬하면 된다.

    정렬로직은 아래 코드의 Word 클래스 내 비교메소드를 참고하면 된다.

     


    코드

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.HashMap;
    import java.util.StringTokenizer;
    
    public class Main {
    
        int N;
        int M;
        HashMap<String, Integer> hashMap;
        ArrayList<Word> words;
    
        public void solution() throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringBuilder sb = new StringBuilder();
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
    
            hashMap = new HashMap<>();
            for (int i = 0; i < N; i++) {
                String input = br.readLine();
                if (input.length() < M) {
                    continue;
                }
    
                hashMap.put(input, hashMap.getOrDefault(input, 0) + 1);
            }
    
            words = new ArrayList<>();
            for (String s : hashMap.keySet()) {
                words.add(new Word(s, hashMap.get(s)));
            }
    
            Collections.sort(words);
    
            for (Word word : words) {
                sb.append(word.spelling).append('\n');
            }
    
            System.out.print(sb);
        }
    
        public static void main(String[] args) throws IOException {
            new Main().solution();
        }
    
        static class Word implements Comparable<Word> {
            String spelling;
            int cnt;
    
            public Word(String spelling, int cnt) {
                this.spelling = spelling;
                this.cnt = cnt;
            }
    
            @Override
            public int compareTo(Word o) {
                if (this.cnt == o.cnt) {
                    if (this.spelling.length() == o.spelling.length()) {
                        return this.spelling.compareTo(o.spelling);
                    }
                    return Integer.compare(o.spelling.length(), this.spelling.length());
                }
                return Integer.compare(o.cnt, this.cnt);
            }
        }
    }

    댓글