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

리뷰

시간초과

• 문자열과 중복 개수를 HashMap에 넣는 부분에서 시간 초과가 발생했다. List에 문자열을 모두 입력받은 후 Set에 저장해 중복을 제거하고 Set을 Iterator 반복문을 돌려 각 문자열이 원본 List에 몇개씩 있는지 체크했다.

 

시간초과 문제를 해결하기 위해 getOrDefault메소드를 사용하여 입력과 동시에 빈도수를 카운트하도록 했다.

 

공부한 것

• getOrDefault(Object key, V DefaultValue)

: map에 key가 있으면 value리턴, 없으면 defalutValue리턴

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

 

• 정렬 비교

숫자 비교 : 래퍼클래스.compare(비교대상1, 비교대상2);

문자 비교 : 비교대상1.compareTo( 비교대상2 );

if (hm.get(o1) != hm.get(o2)) {
				if (o1.length() != o2.length()) {
					return Integer.compare(o2.length(), o1.length());
					// return o2.length() - o1.length();
				}
				return o1.compareTo(o2);

 

 

문제

화은이는 이번 영어 시험에서 틀린 문제를 바탕으로 영어 단어 암기를 하려고 한다. 그 과정에서 효율적으로 영어 단어를 외우기 위해 영어 단어장을 만들려 하고 있다. 화은이가 만들고자 하는 단어장의 단어 순서는 다음과 같은 우선순위를 차례로 적용하여 만들어진다.

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

 �$M$보다 짧은 길이의 단어의 경우 읽는 것만으로도 외울 수 있기 때문에 길이가 �$M$이상인 단어들만 외운다고 한다. 화은이가 괴로운 영단어 암기를 효율적으로 할 수 있도록 단어장을 만들어 주자.

입력

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

둘째 줄부터 �+1$N+1$번째 줄까지 외울 단어를 입력받는다. 이때의 입력은 알파벳 소문자로만 주어지며 단어의 길이는 10$10$을 넘지 않는다.

단어장에 단어가 반드시 1개 이상 존재하는 입력만 주어진다.

출력

화은이의 단어장에 들어 있는 단어를 단어장의 앞에 위치한 단어부터 한 줄에 한 단어씩 순서대로 출력한다.

예제 입력 1 복사

7 4
apple
ant
sand
apple
append
sand
sand

예제 출력 1 복사

sand
apple
append

예제 입력 2 복사

12 5
appearance
append
attendance
swim
swift
swift
swift
mouse
wallet
mouse
ice
age

예제 출력 2 복사

swift
mouse
appearance
attendance
append
wallet

 

내 답안

1.  List에 문자열을 모두 입력받은 후 Set에 저장해 중복을 제거하고 Set을 Iterator 반복문을 돌려 각 문자열이 원본 List에 몇개씩 있는지 계산 (시간초과)

//시간초과 부분
for (int i = 0; i < n; i++) {
			String word = br.readLine();
			if (word.length() >= m) {
				list.add(word);
				hs.add(word);
			}
		}
		Iterator iter = hs.iterator();
		while (iter.hasNext()) {
			String temp = String.valueOf(iter.next());
			hm.put(temp, Collections.frequency(list, temp));
		}

 

2. getOrDefault(Object key, V DefaultValue) 사용

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.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.StringTokenizer;

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));
		StringTokenizer token = new StringTokenizer(br.readLine());
		HashMap<String, Integer> hm = new HashMap<>();
		int n = Integer.parseInt(token.nextToken());
		int m = Integer.parseInt(token.nextToken());
		for (int i = 0; i < n; i++) {
			String word = br.readLine();
			if (word.length() >= m) {
				//getOrDefault(Object key, V DefaultValue) :map에 key가 있으면 value리턴, 없으면 defalutValue리턴 - 
				Integer count = hm.getOrDefault(word, 0);
				hm.put(word, count + 1);
			}
		}

		List<String> keyList = new ArrayList<>(hm.keySet());
		keyList.sort(new Comparator<String>() {
			@Override
			public int compare(String o1, String o2) {
				// 빈도수가 다르면 빈도수 기준으로 역순 정렬
				if (hm.get(o1) != hm.get(o2)) {
					return Integer.compare(hm.get(o2), hm.get(o1));
					// return hm.get(o2) - (hm.get(o1));
				}
				// 빈도수는 같고 문자열 길이는 다르면 길이를 기준으로 역순 정렬
				if (o1.length() != o2.length()) {
					return Integer.compare(o2.length(), o1.length());
					// return o2.length() - o1.length();
				}
				// 빈도수와 문자열 길이가 모두 같다면 문자열 기준으로 사전순(알페벳순) 정렬
				return o1.compareTo(o2);
			}
		});
		for (String key : keyList) {
			bw.write(key + "\n");
		}
		bw.flush();
	}
}