[자바] 백준 20920 - 영단어 암기는 괴로워 (java)

목차

• 문제 : boj20920
• 필요 알고리즘
• 풀이
• 코드 : github

문제 : boj20920

 

 

필요 알고리즘

• 정렬, 해시를 사용한 집합과 맵
  
  • 해당 단어가 몇 번 나왔는지 알기 위해 HashMap을 쓸 수 있어야 한다(다른 방법들도 있긴하다). 그 외에는 문제에서 제시된 방법대로 정렬이 가능한지 묻는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  내 경우엔 Word라는 클래스를 만들고 name이 단어, cnt가 해당 단어가 몇 번 나왔는지를 뜻하도록 했다. 우선은 동일한 단어가 얼마나 나왔는지 알 수 있어야 한다. String에 대한 판단이므로, HashMap을 쓰는게 가장 간단하다.

while (n-->0) {
    String cur = br.readLine();	// 현재 입력받은 단어
    if (cur.length() < m) continue;	// 길이가 M 이하라면 무시

    if (map.containsKey(cur)) {	// HashMap에 이미 존재한다면 
        map.get(cur).count();	// 카운팅만 해준다.
        continue;
    }

    Word word = new Word(cur);	// HashMap에 없다면 객체를 생성하고
    list.add(word);	// 리스트와
    map.put(cur, word);	// HashMap에 넣어준다.
}

 

  해시맵을 통해 Word 클래스 리스트를 만들었다. 그럼 이제 문제에 제시된 방식대로 정렬만 잘 해주면 된다. 자바의 경우 Comparable을 구현해주거나, Collections.sort 함수의 2번째 인자로 Comparator를 구현해서 넣어주면 커스텀한 방식으로 정렬시킬 수 있다. 이하 1,2,3 순서대로 적혀있는게 중요하다. 문제에서 제시된 순서대로 정렬해야 문제에서 제시된 규칙대로 정렬시킬 수 있다.

@Override
public int compareTo(final Word o) {
    if (this.cnt != o.cnt) {	// 1. 자주 나오는 단어일수록 앞에 배치
        return o.cnt - this.cnt;
    }

    if (this.name.length() != o.name.length()) {	// 2. 해당 단어의 길이가 길수록 앞에 배치
        return o.name.length() - this.name.length();
    }

    return this.name.compareTo(o.name);	// 3. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치
}

 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        List<Word> list = new ArrayList<>();
        Map<String, Word> map = new HashMap<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        while (n-->0) {
            String cur = br.readLine();
            if (cur.length() < m) continue;

            if (map.containsKey(cur)) {
                map.get(cur).count();
                continue;
            }

            Word word = new Word(cur);
            list.add(word);
            map.put(cur, word);
        }

        Collections.sort(list);
        StringBuilder sb = new StringBuilder();
        for (Word word : list) {
            sb.append(word.name).append('\n');
        }
        System.out.print(sb);
    }
}

class Word implements Comparable<Word> {
    String name;
    int cnt;

    public Word(String name) {
        this.name = name;
        cnt = 1;
    }

    public void count() {
        this.cnt++;
    }

    @Override
    public int compareTo(final Word o) {
        if (this.cnt != o.cnt) {
            return o.cnt - this.cnt;
        }

        if (this.name.length() != o.name.length()) {
            return o.name.length() - this.name.length();
        }

        return this.name.compareTo(o.name);
    }
}