컴퓨터/백준 알고리즘

백준 알고리즘 - 20920번: 영단어 암기는 괴로워 [Java]

이상한 나그네 2023. 10. 12. 00:50

문제: 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

1. 코드

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));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		Set <String> set = new TreeSet<>();
		Map <String, Integer> map = new HashMap<>();
		while(N-- > 0) {
			String s = br.readLine();
			if(s.length() >= M) {
				set.add(s);
				if(map.containsKey(s))
					map.put(s, map.get(s) + 1);
				else
					map.put(s, 1);
			}
		}
		List <String> list = new ArrayList<>(set);
		Collections.sort(list, (a, b)->b.length() - a.length());
		Collections.sort(list, (a, b)->map.get(b) - map.get(a));
		
		StringBuilder sb = new StringBuilder();
		for(String s : list)
			sb.append(s).append('\n');
		System.out.println(sb.toString());
	}
}

2. 설명

Set <String> set = new TreeSet<>();
Map <String, Integer> map = new HashMap<>();
while(N-- > 0) {
    String s = br.readLine();
    if(s.length() >= M) {
        set.add(s);
        if(map.containsKey(s))
            map.put(s, map.get(s) + 1);
        else
            map.put(s, 1);
    }
}

TreeSet을 이용하여 문자열의 중복 제거와 알파벳 순서로 정렬을 입력과 동시에 진행합니다. HashMap을 이용하여 영단어의 빈번도를 확인합니다.

List <String> list = new ArrayList<>(set);
Collections.sort(list, (a, b)->b.length() - a.length());
Collections.sort(list, (a, b)->map.get(b) - map.get(a));

이미 영단어의 알파벳을 기준으로 오름차순으로 정렬이 된 상태에서 길이를 기준으로 오름차순으로 정렬한 뒤 빈번도를 기준으로 오름차순으로 정렬합니다.

StringBuilder sb = new StringBuilder();
for(String s : list)
    sb.append(s).append('\n');
System.out.println(sb.toString());

StringBuilder를 사용하여 문자열을 한번에 저장한 뒤 출력해주면 문제는 해결됩니다.

3. 정리

  1. Collections.sort()에 대해서 알고 있으면 쉽게 해결할 수 있다.