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

1. 문제

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

주어진 영어 단어들 중에서 길이가 M 이상인 단어만 선택해 다음 조건에 따라 정렬한 후, 단어장을 만드는 문제이다.

정렬 우선순위
1. 자주 나오는 단어일수록 앞에 배치
2. 단어 길이가 길수록 앞에 배치
3. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치

2. 풀이

📝 1차 시도

class Word {
    String word;
    int frequency;
    int length;
    Word(String word, int frequency, int length) {
        this.word = word;
        this.frequency = frequency;
        this.length = length;
    }
}

단어와 단어의 등장 빈도, 길이를 저장하는 Word 클래스를 생성한다.

List<Word> words = new ArrayList<>();
for (int i = 0; i < n; i++) {
    String s = br.readLine();
    if (s.length() < m) continue; 

단어를 입력받아 길이가 m보다 크면 처리하고, 작으면 무시한다.

if (words.isEmpty() || !isExist(s, words)) {
    words.add(new Word(s, 1, s.length()));
} else {
    for (Word w : words) {
        if (w.word.equals(s)) {
            w.frequency++;
        }
    }
}

isExist(s, words) 메서드를 통해 이미 등록된 단어인지 확인하고, 없다면Word 객체를 만들어 리스트에 추가, 존재하면 빈도를 1 증가시킨다.

Collections.sort(words, (a, b) -> {
    if (a.frequency != b.frequency)
        return b.frequency - a.frequency; 
    if (a.length != b.length)
        return b.length - a.length; 
    return a.word.compareTo(b.word); 
});

정렬 우선순위에 따라 words를 정렬한다.

for (Word w : words) {
    System.out.println(w.word);
}

정렬된 단어 목록을 하나씩 출력한다.

public static boolean isExist(String s, List<Word> words) {
    for (Word w : words) {
        if (w.word.equals(s)) return true;
    }
    return false;
}

입력된 단어가 words 리스트에 이미 존재하는지 확인하는 메서드이다.

=> 시간초과

❌ 문제점

if (words.isEmpty() || !isExist(s, words)) {
    words.add(new Word(s, 1, s.length()));
} else {
    for (Word w : words) {
        if (w.word.equals(s)) {
            w.frequency++;
        }
    }
}

입력받은 단어의 중복 확인과 빈도 증가를 위해 리스트를 탐색하는 과정에서 O(N)의 시간이 소요되며, 이를 모든 입력 단어에 대해 반복하므로 O(N^2)의 시간 복잡도가 발생한다. 이로 인해 입력이 많아질수록 시간 초과가 발생하게 된다.

for (Word w : words) {
    System.out.println(w.word);
}

단어의 수만큼 System.out.println을 호출하기 때문에 출력이 한 번에 처리되지 않고, 각 호출마다 I/O 작업이 발생한다. 각 출력이 완료될 때까지 다른 작업이 지연되므로, 입력 데이터가 많을수록 실행 시간이 크게 늘어나는 원인이 된다.

🛠️ 2차 시도

Map<String, Integer> words = new HashMap<>();
for (int i=0; i<n; i++) {
	String s = br.readLine();
	if (s.length() < m) continue;
	if (words.isEmpty() || !words.containsKey(s)) {
		words.put(s, 1);
	} else {
		words.replace(s, words.get(s) + 1);
	}
}

HashMap을 사용하여 중복 체크와 빈도 증가를 O(1) 시간에 처리하였다.

List<String> list = new ArrayList<>(words.keySet());
Collections.sort(list, (a, b) -> {
    if (!words.get(a).equals(words.get(b))) 
        return words.get(b) - words.get(a);  
    if (a.length() != b.length()) 
        return b.length() - a.length();     
    return a.compareTo(b);                  
});

Map의 KeySet()을 리스트로 변환하고 정렬 우선순위에 따라 리스트를 정렬하였다.

StringBuilder sb = new StringBuilder();
for (String s : list) {
    sb.append(s).append("\n");
}
System.out.println(sb);

System.out.println 대신 StringBuilder를 사용해 문자열을 누적하고, 최종적으로 한 번만 출력하도록 개선하였다.

3. 소스 코드

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

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> words = new HashMap<>();
        for (int i=0; i<n; i++) {
            String s = br.readLine();
            if (s.length() < m) continue;
            if (words.isEmpty() || !words.containsKey(s)) {
                words.put(s, 1);
            } else {
                words.replace(s, words.get(s) + 1);
            }
        }
        
        List<String> list = new ArrayList<>(words.keySet());
        Collections.sort(list, (a, b) -> {
            if (words.get(a) != words.get(b))
                return words.get(b) - words.get(a); 
            if (a.length() != b.length())
                return b.length() - a.length(); 
            return a.compareTo(b); 
        });
        
        StringBuilder sb = new StringBuilder();
        for (String s : list) {
            sb.append(s).append("\n");
        }
        System.out.println(sb);
    }
}