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

👀 문제 분석

백준 - 영단어 암기는 괴로워

아래 조건에 맞춰 단어의 순서를 정하고 영어 단어장을 만든다.

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

단! 입력된 M보다 긴 길이의 단어들만 포함한다.

⚒️ 설계

1. 공백을 기준으로 단어의 개수(N)와 외울 단어 기준 길이(M)를 입력받는다.
2. 단어 - 수 로 매핑한다.
   1. 먼저 M보다 적은 길이의 단어는 거른다.
   2. 빈도수를 계산하여 빈도수가 높은 순서로 배치한다.
   3. 빈도수가 동일하다면 단어의 길이를 기준으로 배치한다.
   4. 빈도수도 동일하고 단어의 길이도 동일할 경우 알파벳 사전 순으로 배치한다.
3. 배치된 단어장을 반환한다.

📝 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        Map<String, Integer> wordFrequency = getWordFrequency(br);

        List<String> wordList = getWordList(wordFrequency);

        for (String word : wordList) {
            bw.write(word);
            bw.newLine();
        }

        bw.flush();
        bw.close();
        br.close();
    }

    private static Map<String, Integer> getWordFrequency(BufferedReader br) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        Map<String, Integer> wordFrequency = new HashMap<>();

        for (int i = 0; i < n; i++) {
            String word = br.readLine();

            if (word.length() >= m) {
                wordFrequency.put(word, wordFrequency.getOrDefault(word, 0) + 1);
            }
        }

        return wordFrequency;
    }

    private static List<String> getWordList(final Map<String, Integer> wordFrequency) {
        List<String> wordList = new ArrayList<>(wordFrequency.keySet());

        wordList.sort((w1, w2) -> {
            int freqCompare = wordFrequency.get(w2).compareTo(wordFrequency.get(w1));
            if (freqCompare != 0) {
                return freqCompare;
            }

            int lengthCompare = Integer.compare(w2.length(), w1.length());
            if (lengthCompare != 0) {
                return lengthCompare;
            }

            return w1.compareTo(w2);
        });

        return wordList;
    }
}

⌛️ 시간복잡도

• 빈도수 계산 : O(N)
• 정렬 : 필터링된 단어의 수 K라고 하면 O(K log K)

👩🏻‍💻 느낀점

처음에 비교해야할 조건이 많아서 복잡할 줄 알았는데 Comparator를 사용하니 어렵지 않았다.

BufferedWriter와 System.out.println()의 성능 차이는 대용량 데이터가 들어올 때 효율적인 것 같다.

해당 문제에서는 여러 문자열들을 다루기 때문에 BufferedWriter를 사용하면 메모리 효율성을 높일 수 있을 것이라고 판단했다.

잊지 말아야 할 것은 리소스 누수 방지를 위해 꼭 close()를 해주어야한다는 것이다!!!!

✔️ 소요 시간: 30분