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

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

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

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.StringTokenizer;

public class P20920 {

	static class Word {
		String spell;
		int count;

		public Word(String spell) {
			this.spell = spell;
			this.count = 1;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		HashMap<String, Integer> wordIdx = new HashMap<>();
		int idx = 0;
		ArrayList<Word> arr = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			// 단어를 하나씩 입력받음
			String now = br.readLine();

			// m글자 미만은 외우지 않음
			if (now.length() < m)
				continue;

			if (wordIdx.get(now) == null) {
				arr.add(new Word(now));
				wordIdx.put(now, idx++);
			} else {
				arr.get(wordIdx.get(now)).count++;
			}
		}

		Collections.sort(arr, new Comparator<Word>() {

			@Override
			public int compare(P20920.Word o1, P20920.Word o2) {
				if (o1.count == o2.count) {
					if (o1.spell.length() == o2.spell.length()) {
						return o1.spell.compareTo(o2.spell);// 사전순 오름차순
					}
					return o2.spell.length() - o1.spell.length();// 단어 길이순 내림차순
				}
				return o2.count - o1.count; // 나온횟수 내림차순
			}
		});

		for (int i = 0; i < arr.size(); i++) {
			bw.append(arr.get(i).spell + "\n");
		}
		bw.flush();
		bw.close();
		br.close();
	}

}

우선 각 단어는 Word라는 클래스를 이용하여 표현할 수 있다.

각 단어는 철자를 spell에 저장하고,

나온 횟수를 count에 저장한다. (count의 초기값은 1이다)

 

단어를 입력받고,

단어가 m글자 미만이라면 버린다.

 

처음 나온 단어라면 ArrayList에 저장하고,

HashMap에 {단어:ArrayList에 저장한 인덱스}를 쌍으로 저장해둔다.

(그러면 이미 존재하는 단어가 나왔을 때, hashmap에서 단어를 검색하고 arrayList의 몇번째 인덱스에 있는지 O(1)만에 찾을 수 있다)

 

이미 나온 적 있는 단어라면(hashmap에 해당 단어가 존재하는 경우)

ArrayList에서 해당 단어를 찾아 count를 1 증가시킨다.

(해당 단어가 arrayList에서 몇 번째 인덱스에 있는지는 hashmap에서 get메소드로 알 수 있다)

 

이렇게 단어들을 중복 없이 arrayList에 저장한다.

 

저장이 끝났다면, 정렬을 해 주어야 한다.

내가 선언한 Word클래스의 객체를 정렬하기 위해서는 comparator 오버라이딩을 해야한다.

		Collections.sort(arr, new Comparator<Word>() {

			@Override
			public int compare(P20920.Word o1, P20920.Word o2) {
				if (o1.count == o2.count) {
					if (o1.spell.length() == o2.spell.length()) {
						return o1.spell.compareTo(o2.spell);// 사전순 오름차순
					}
					return o2.spell.length() - o1.spell.length();// 단어 길이순 내림차순
				}
				return o2.count - o1.count; // 나온횟수 내림차순
			}
		});

가장 먼저 나온 횟수를 비교하고,

나온 횟수(count)가 같다면 철자의 길이를,

철자의 길이도 같다면 사전순으로 비교한다.

 

이 때 사전순 비교는

String.compareTo메소드를 이용하면 된다.

(str1.compareTo(str2)를 했을 때, str1이 사전순으로 앞에 있다면 -1을, 같다면 0을, 사전순으로 뒤에있다면 1을 반환하는 함수이다.)