[백준 / BOJ] 20920 영단어 암기는 괴로워

문제

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

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

영어 단어장에 N개의 단어가 적혀있다.

화은이는 단어장에있는 N개의 단어들중 K개의 길이 이상의 단어를 다음 순서에따라 정렬할려고한다.

 

1. 자주 나오는 단어순으로 정렬한다.

2. 단어의 길이가 길수록 앞으로 배치한다.

3. 알파벳 사전 순으로 앞에있는 단어일수록 앞에 배치한다.

 

N과 K, N개의 단어가 주어졌을때, 정렬된 결과를 출력하는 문제다.

 

---

풀이

N이 10만이라서 완전탐색으로 풀경우, N^2으로 시간초과가 나온다.

 

몇가지 풀이방법을 생각해볼수있었는데,

 

1. HashMap으로 탐색마다 단어가 있는지 확인후, 있다면, 단어를 키로 갖는 value를 증가시킨다.

 

2. 두번 정렬한다.

 

1번이 시간은 더 짧게 걸리지만(아마 정렬 1번차이일것같음), 구현상 편한 2번으로 풀었다. 아이디어는 다음과 같다.

 

문자열을 정렬하면, 사전순으로 정렬이된다. 즉, 같은 문자끼리 붙어있는 상태가되는데, 이렇게되면, 1번 정렬후, N번탐색으로 모든 문자열의 빈도수를 체크해줄수있다.

 

예를들어, 단어장의 단어가 다음과 같다고 하자.

 

ABC

ABCD

ABC

ABC

DEF

 

위 상태에서 ABC가 등장하는 빈도를 체크한다고 하면, 우리는 ABC가 어느 idx에 위치할지 모르므로, 모든 idx를 탐색해야한다. 그 후, ABCD의 빈도를 찾기위해 다시 모든 idx를 찾는 과정이 반복되어서 N^2번 반복하게된다. 하지만, 위 단어장을 정렬하면,

 

ABC

ABC

ABC

ABCD

DEF

 

상태가 되고, 처음 ABC가 나온이후, 다른 단어가 나온다면, 더 이상 ABC는 나오지 않을거라는것을 알수있다.

 

즉, 1번 정렬후, 빈도수, 길이, 사전순을 기준으로 1번 더 정렬하면 답을 구할수있다.

 

주요 소스코드

    public void setFrqDictionary(){
        frequency frq = new frequency(dictionary.get(0),1);
        for(int i = 1; i < dictionary.size(); i++){
            if(!frq.word.equals(dictionary.get(i))){
                frqDictionary.add(frq);
                frq = new frequency(dictionary.get(i),1);
            }
            else frq.add();
        }
        frqDictionary.add(frq); 
        Collections.sort(frqDictionary);
    }

 

이렇게 시간을 줄이더라도, System.out 으로 출력하면 시간초과가 나오는 문제였따.

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/20920%20%EC%98%81%EB%8B%A8%EC%96%B4%20%EC%95%94%EA%B8%B0%EB%8A%94%20%EA%B4%B4%EB%A1%9C%EC%9B%8C/Main.java

devxb/JJUNalgo