목차
문제 정보
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
난이도 : S3
유형 : 정렬, 해쉬
문제 풀이
문자들을 우선순위에 따라 정렬하는 것이 이 문제의 핵심이다.
일단 해쉬맵을 이용하여 문자열을 처리해야한다.
해쉬맵의 getOrDefault() 메소드를 활용하여 개수를 처리
해쉬맵의 데이터를 리스트로 전달하고
구현한 정렬로직을 통하여 리스트를 정렬하면 된다.
정렬로직은 아래 코드의 Word 클래스 내 비교메소드를 참고하면 된다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.StringTokenizer;
public class Main {
int N;
int M;
HashMap<String, Integer> hashMap;
ArrayList<Word> words;
public void solution() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
hashMap = new HashMap<>();
for (int i = 0; i < N; i++) {
String input = br.readLine();
if (input.length() < M) {
continue;
}
hashMap.put(input, hashMap.getOrDefault(input, 0) + 1);
}
words = new ArrayList<>();
for (String s : hashMap.keySet()) {
words.add(new Word(s, hashMap.get(s)));
}
Collections.sort(words);
for (Word word : words) {
sb.append(word.spelling).append('\n');
}
System.out.print(sb);
}
public static void main(String[] args) throws IOException {
new Main().solution();
}
static class Word implements Comparable<Word> {
String spelling;
int cnt;
public Word(String spelling, int cnt) {
this.spelling = spelling;
this.cnt = cnt;
}
@Override
public int compareTo(Word o) {
if (this.cnt == o.cnt) {
if (this.spelling.length() == o.spelling.length()) {
return this.spelling.compareTo(o.spelling);
}
return Integer.compare(o.spelling.length(), this.spelling.length());
}
return Integer.compare(o.cnt, this.cnt);
}
}
}
'Algorithm, Problem Solving > 백준(boj)' 카테고리의 다른 글
[백준][Java] 2799 - 블라인드 (0) | 2023.12.09 |
---|---|
[백준][Java] 17175 - 피보나치는 지겨웡~ (0) | 2023.12.07 |
[백준][Java] 6907 - Floor Plan (0) | 2023.10.19 |
[백준][Java] 5107 - 마니또 (0) | 2023.10.15 |
[백준][Java] 23288 - 주사위 굴리기 2 (0) | 2023.10.12 |
댓글