[BaekJoon] 백준 20920번 _ 영단어 암기는 어려워 for JAVA

 

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

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

 

 

문제

 

 

---

 

오랜만에 푸는 알고리즘......ㅎㅎ

 

map에는 다양한 메소드가 많은데 맨날 put get contains 이런거만 쓰는 것 같아서 언제한번 정리해보려고 한다.

 

 

아무튼 풀이를 해보자면

 

사실 신경써야하는건 얘네가 정렬되는 순서이다.

 

 

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

 

 

이렇게임

 

Comparable<>을 오버라이딩해서 정렬 시 저 순서대로 정렬해주면 되는 간단한 문제이다.

 

 

Comparable 오버라이딩 할 때 return값이 양수이면 앞, 음수이면 뒤쪽으로 배치된다.

 

그러니까 1,2번은 내림차순이니까 (들어오는 객체 - 현재객체) 순으로 return 해줘야한다.

 

그리고 compareTo() 사용하면 단어 사전순으로 정렬할 수 있다.

 

만약 a.compareTo(b) 일 때 매개변수 문자열, 즉 b가 더 크면 음수, 반대면 양수가 나온다. (같으면 0)

 

 

따라서 사전순으로 배치해야하므로 들어오는애가 매개변수로 들어가야 한다.

 

 

 

 

코드

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

public class Main {
	
	static class Words implements Comparable<Words>{
		String word;
		int cnt;
		
		public Words(String word, int cnt) {
			this.word = word;
			this.cnt = cnt;
		}

		@Override
		public int compareTo(Words o) {
			if(this.cnt != o.cnt) return o.cnt - this.cnt;
			else if(o.word.length() != this.word.length()) return o.word.length() - this.word.length();
			return this.word.compareTo(o.word);
		}	
	}

	public static void main(String[] args) throws Exception {
		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());
		
		HashMap<String, Integer> map = new HashMap<>();
		
		for(int i=0; i<N; i++) {
			String input = br.readLine();
			if(input.length() < M) continue;
			
			if(!map.containsKey(input)) {
				map.put(input, 1);
			} else {
				int value = map.get(input);
				map.replace(input, value+1);
			}
		}
		
		/* */
		ArrayList<Words> list = new ArrayList<>();
		map.forEach((key, value) -> {
			list.add(new Words(key, value));
		});
		Collections.sort(list);
		
		StringBuilder sb = new StringBuilder();
		for(Words word : list) {
			sb.append(word.word).append('\n');
		}
		
		System.out.println(sb.toString());
		
	}

}

 

성능

 

 

 

이렇게 풀어봤다.

 

 

 

 

근데 뭔가.. 저거 하나때문에 클래스를 만드는거 뭔가 비효율적인 것 같기도 하네요..

 

 

 

그래서 다른 사람 풀이를 보고 고쳐보기로 했다.

 

 

import java.util.*;
import java.util.stream.Collectors;
import java.io.*;

public class Main {

	public static void main(String[] args) throws Exception {
		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());
		
		HashMap<String, Integer> map = new HashMap<>();
		
		for(int i=0; i<N; i++) {
			String input = br.readLine();
			if(input.length() < M) continue;
			
			int value = map.getOrDefault(input, 0);
			map.put(input, value+1);
		}
		
		/* */
		ArrayList<String> lists = (ArrayList<String>) map.keySet().stream().collect(Collectors.toList());
		
		lists.sort((o1,o2) -> {
			int v1 = map.get(o1);
			int v2 = map.get(o2);
			
			if(v1 == v2) {
				if(o1.length() == o2.length()) {
					return o1.compareTo(o2);
				}
				return o2.length() - o1.length();
			}
			return v2-v1;
		});
		
		StringBuilder sb = new StringBuilder();
		for(String list : lists) {
			sb.append(list).append('\n');
		}
		
		System.out.println(sb.toString());
		
	}
}

 

성능

 

 

 

성능이 좋아지진 않았다!!!

 

stream도 여러 메소드를 지원해서 좋은듯. 얘도 나중에 공부해봐야지~