문제 url:
영단어 암기는 괴로워
문제:
🤔 문제 알아보기
문제를 읽어봤을 때 우리가 구해야 하는 조건을 풀어본다면,
먼저 단어 개수 N과 최소 단어 길이 M이 주어진다.
그리고, N개의 단어를 입력받는데 여기서 최소 M의 길이 이상의 단어만 저장한다.
그렇게 모은 단어를 3가지 조건에 따라 정렬을 하는 문제이다
- 1번 조건: 자주 나오는 단어는 앞에 배치
- 2번 조건: 해당 단어의 길이가 길수록 앞에 배치
- 3번 조건: 알파뱃 사전 순으로 앞에 있는 단어일수록 앞에 배치
우리는 일단 키워드로 단어 와 배치 를 보고 단어 정렬을 떠올릴 수 있는데,
그러면 우리는 Arrays.sort() 혹은 Collections.sort() 메서드중에서
comparactor 인터페이스를 구현해 조건에 따른 정렬을 할 필요가 있다.
comparactor 인터페이스를 통해 2번, 3번 조건은 만들 수 있지만, 1번 조건을 만들 수는 없다.
그래서 우리는 단어의 개수를 세고 각 단어의 개수를 효과적으로 보관할 수 있는 HashMap자료구조를 사용하고자 한다.
Map 자료구조란:
key-value pair로 이루어져, key에 따른 value값을 보관할 수 있는 자료구조이다.
- key는 중복을 허용하지 않지만, value는 중복값을 가질 수 있다.
- key가 중복을 허용하지 않기 때문에 중복값 제거에 효과적
자 여기까지 필자가 생각했던 방식이다. 하지만, 정렬방식을 구현하지 못해 결국 여러 블로그의 힌트들을 참조하며 코드를 작성해보았다.
🐱👤 실제 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
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> map = new HashMap<>();
for(int i = 0; i < N; i++) {
String word = br.readLine();
if(word.length() >= M) {
map.put(word, map.getOrDefault(word, 0) + 1);
}
}
List<String> word_list = new ArrayList<>(map.keySet());
word_list.sort((o1, o2) -> {
/*
* 1. 조건: 자주 나오는 단어일수록 앞에 배치
* 자주 나오는 단어를 맨 상단에 놔두기 위한 작업
* 두 수를 비교했을 때, 같지 않다면(즉, 자주 나오는 단어가 아니라면)
*/
if (Integer.compare(map.get(o1), map.get(o2)) > 0) {
return -1;
} else if(Integer.compare(map.get(o1), map.get(o2)) < 0) {
return 1;
}
/*
* 2. 조건: 해당 단어의 길이가 길수록 앞에 배치
* 단어의 길이가 첫 번째 단어가 길다면 (앞에 배치된 것이기 때문에 정렬하지 않음)
* 그래서 -1을 반환
* 단어의 길이가 첫 번째 단어가 짧다면 (뒤로가야 하는 즉, 정렬되어야 하기 때문에)
* 그래서 1을 반환
*/
if (o1.length() > o2.length()) {
return -1;
} else if (o1.length() < o2.length()) {
return 1;
}
/*
* 3. 조건: 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치
*/
return o1.compareTo(o2);
});
StringBuilder sbd = new StringBuilder();
for(String val : word_list) {
sbd.append(val).append("\n");
}
System.out.println(sbd);
}
}
최대한 주석으로 설명을 해놨지만, 그래도 주요 로직을 풀이해보겠다.
😎 코드 해석 및 풀이
1번 로직
Map<String,Integer> map = new HashMap<>();
for(int i = 0; i < N; i++) {
String word = br.readLine();
if(word.length() >= M) {
map.put(word, map.getOrDefault(word, 0) + 1);
}
}
먼저, 해당 로직은 Map에 단어의 개수를 세고 저장하는 로직이다.
문제 조건에 따라 단어 길이 M 이상의 단어만 저장하는데,
여기서 getOrDefault()메서드를 활용하여, 개수를 더해나갈 수 있다.
getOrDefault() 메서드:
map에 key에 대한 value가 존재한다면 해당값을 반환, 그렇지 않으면 default 값을 반환.
그래서 해당 문구에서는 값이 존재하지 않으면 0을 반환하여 0+1을 하여
초기값 1이 들어가는 것이다.
2번로직
List<String> word_list = new ArrayList<>(map.keySet());
word_list.sort((o1, o2) -> {
/*
* 1. 조건: 자주 나오는 단어일수록 앞에 배치
* 자주 나오는 단어를 맨 상단에 놔두기 위한 작업
* 두 수를 비교했을 때, 같지 않다면(즉, 자주 나오는 단어가 아니라면)
*/
if (Integer.compare(map.get(o1), map.get(o2)) > 0) {
return -1;
} else if(Integer.compare(map.get(o1), map.get(o2)) < 0) {
return 1;
}
/*
* 2. 조건: 해당 단어의 길이가 길수록 앞에 배치
* 단어의 길이가 첫 번째 단어가 길다면 (앞에 배치된 것이기 때문에 정렬하지 않음)
* 그래서 -1을 반환
* 단어의 길이가 첫 번째 단어가 짧다면 (뒤로가야 하는 즉, 정렬되어야 하기 때문에)
* 그래서 1을 반환
*/
if (o1.length() > o2.length()) {
return -1;
} else if (o1.length() < o2.length()) {
return 1;
}
/*
* 3. 조건: 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치
*/
return o1.compareTo(o2);
});먼저, List<String> word_list = new ArrayList<>(map.keySet());
keySet() 메서드를 통해 map에 존재하는 키값을 ArrayList 클래스에 담은 후 선언한다.
그런 다음 Collections.sort()를 진행하는데,
필자는 comparactor 인터페이스를 익명함수로 구현한 것이 아닌, 람다 형식으로 구현하여 조금 다르게 보인다. 하지만 원리는 비슷하기 때문에 계속 설명하면
리스트 안 o1과 o2 변수를 이용하여 아래의 조건을 진행한다.
첫번쨰 조건인 Inter.parse()메서드는 두 값을 비교하여 x가 작으면 -1 같으면 0 x가 크면 1을 반환하는 메서드이다.
그래서 만약 o1이 o2보다 크다면? 개수가 더 많은 것이기 때문에 정렬대상이 아니다. 그래서 return -1을 진행하는 것. else if문도 동문이다.
그러면 이제 남는 조건은 x와 y가 같은 경우 즉 0인 경우가 남는데
그때는 이제 아래의 조건을 수행하게 된다.
- 길이가 긴 경우
- 사전 순 정렬
길이가 긴 경우도 마찬가지로 o1과 o2를 비교했을 때,
o1의 길이가 긴 경우, 오름차순이 된 상태이므로 정렬 대상이 아니라 -1을 반환
o1의 길이가 짧은 경우, 정렬 대상이므로 1을 반환하여 길이가 긴 o2가 앞에 오도록 한다.
그런 다음 길이가 같은 경우 o1.compareTo(o2)를 return하게 되는 것이다.
str.compareTo(another str) 메서드는, 문자열을 사전순으로 비교하여 값을 반환해주는 메서드이다.
🤢 회고
해당 문제를 풀면서 대충 어떻게 풀면 되는지를 생각해보았다.
하지만, comparactor 인터페이스를 구현했던 방식을 많이 잊어버려서 결국은 100%힘으로 풀지는 못하였고, 좀 아쉬움이 많이 남는다.
또한, 더 나은 방식으로 구현할 수 있지 않을까? 하는 생각에 여러 방향으로 풀면서 시간을 지체했으며 Map방식을 떠올리고는 더 나은 방식을 생각해본다고 다른 방향으로 틀면서 코드가 많이 엉켜버리기도 했다.
더 나은 방식도 좋지만, 때로는 처음에 구상했던게 하드 코딩 방식일지라도 구현을 해본 다음 더 나은 방식을 생각해보도록 버릇을 고쳐야겠다.
※이게 정말 중요한 것 같다... 하드 코딩도 때론 도움이 된다는 것을...
또 오히려 하드 코딩 방식이라고 생각했던 구상이 답인 경우가 거의 대다수였기도 했다..
💜 참고자료
[백준] 20920번 : 영단어 암기는 괴로워 – JAVA [자바] <- 이분 베이스로 문제를 풀이 진행
