[PS] BOJ20920 영단어 암기는 괴로워 ( 해시 ) with JAVA

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

 

◎ 문제풀이

 

우선순위로 주어진 3가지 조건에 부합하도록 단어를 나열하는 문제이다. 

 

우선순위가 한 가지가 아니라 3가지를 한번에 고려하여 정렬을 해야하므로 우선순위큐를 발상하였다. 또한 가장 높은 우선순위 조건이 가장 자주 나오는 단어이므로, 동일한 단어가 등장할 때마다 O(1) 시간복잡도로 카운트할 수 있도록 해시맵을 이용하였다. 

 

 

◎ 코드

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

//BOJ20920 영단어 암기는 괴로워
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());

        HashMap<String,Integer> hashMap = new HashMap<>();

        for(int i=0;i<n;i++){
            String str = br.readLine();
            if(str.length() < m) continue;

            if(hashMap.containsKey(str)){
                int count = hashMap.get(str);
                hashMap.replace(str,count+1);
            }else{
                hashMap.put(str,1);
            }
        }

        PriorityQueue<Word> pq = new PriorityQueue<>();
        List<String> keyList = new ArrayList<>(hashMap.keySet());
        for( String key : keyList ){
            pq.add(new Word(key,hashMap.get(key)));
        }

        StringBuilder sb = new StringBuilder();
        while(!pq.isEmpty()){
            sb.append(pq.poll().value).append("\n");
        }

        System.out.println(sb.toString());

    }

    public static class Word implements Comparable<Word>{
        String value;
        int count;

        public Word(String value, int count){
            this.value = value;
            this.count = count;
        }

        @Override
        public int compareTo(Word word){
            if( this.count == word.count ){
                if(this.value.length() == word.value.length()){
                    return this.value.compareTo(word.value);
                }else{
                    return word.value.length() - this.value.length();
                }
            }else{
                return word.count - this.count;
            }
        }
    }
}