[baekjoon 1181번] 정렬 - 단어 정렬

문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

 

예제 입력 1  13 but i wont hesitate no more no more it cannot wait im yours

예제 출력 1 i im it no but more wait wont yours cannot hesitate

---

문제풀이

 

이전 글 좌표 정렬하기 느낀점에서 내가 짠 코드보다 더 나은 코드가 있어서 소개한적이 있었다.

 

그 코드는 List.sort(); 메소드에 new comparator 클래스를 선언하여 그 안에 있는 compare메소드를 오버라이드해서 새로운 규칙의 비교 메소드를 생성하는 형식을 람다로 축소하여 2개 이상의 인자에 대하여 정렬하는 방법을 소개한적 있었다.

 

그래서 이번 문제에서 그 코드를 응용하여 적용해보았는데 위와 같은 13개의 입력값에 대해선 문제없이 작동하는 걸 확인하였다. 아래가 그 코드이다.

 

위 코드는 테스트용 코드로 20000개의 랜덤한 단어들을 문자열로 입력받아서 정렬을 수행하는 코드이다.

 

하지만 위 코드로 테스트를 진행했을 때 실행시간이 거의 2.5~3초 가까이 나왔다.

 

그래서 보기엔 더 심플하고 더 빠르게 될 것만 같았던 코드가 시간초과로 문제를 해결할 수 없자 살짝 뇌정지가 왔었다.

 

그래서 이전에 내가 썼던 방법대로 map을 이용하여 정렬하는 방식을 이용해야겠다는 생각이 들었다.

 

그래서 맵을 이용해서 2개의 인자를 정렬할 때는 다음과 같은 방식으로 진행한다.

 

1. 값을 입력받는다.

 

2. map에 해당 데이터를 입력한다. 이때 만약 같은 값이 있다면 넘어간다.

 

3. 입력받은 데이터의 key 배열을 정렬한다.

 

4. 각 key에 해당하는 value리스트를 정렬한다.

 

5. 각각의 key와 value들을 순서대로 출력한다.

---

1~2.

먼저 n을 입력받고 map을 만든 후 단어들을 입력받는다. 이때 해당key값이 없다면 새로운 list를 추가해준 뒤 값을 입력한다.

 

이때 해당 key값에 문자열 s가 있는지 확인하여 있다면 아무런 동작도 하지 않고 없다면 문자열을 추가한다.

 

이 코드가 내가 위에 썼었던 코드보다 빠르게 동작하는 이유는 위 코드는 값이 들어올 때마다 모든 리스트를 탐색하는 반면 이 코드는 입력된 값이 특정 key에 해당하는 리스트에서만 존재하는지 확인하기 때문에 실행시간이 현저하게 줄어들기 때문이다.

 

 

3.

4.

key값에 해당하는 리스트들을 정렬해준다. 여기서는 문자열만 비교하므로 특별히 new comparator클래스를 만들필요는 없다.

 

5.

그리고 모든 값들을 문자열에 추가한 뒤 해당 문자열을 리턴하면 끝난다.

---

테스트용 단어 생성기 코드

    public static String makerandom(int n) throws IOException 
    {
        Random rand = new Random(System.currentTimeMillis());
        StringBuffer str = new StringBuffer("");
        File file = new File("words.txt");
        FileReader fr = new FileReader(file);
        BufferedReader bufferedReader = new BufferedReader(fr);
        String line = "";
        String[] strArray = new String[466550];
        for(int j = 0; (line = bufferedReader.readLine()) != null ; j++) {strArray[j] = line;}
        int num = 0;
 
        str.append(n+"\n");
        for(int i = 0 ; i < n; i++)
        {
            num = rand.nextInt(466550);
            str.append(strArray[num]+"\n");
 
        }
        return str.toString();
    }    

이 코드는 words.txt라는 텍스트 파일로부터 단어를 n개 만큼 랜덤으로 가져오는 메소드이다. 해당 텍스트 파일의 단어의 갯수가 466550개여서 466550크기의 배열을 생성하였다.

 

https://github.com/dwyl/english-words/blob/master/words.txt

 

위 경로에 가면 다운받을 수 있는 사전 파일이다.

 

---

wordSortUsingMap vs wordSortUsingList

 

wordSortUsingMap은 문제를 해결한 코드이고 wordSortUsingList는 시간 초과가 난 코드이다. 두 코드 간의 시간 차이를 비교해보겠다.

import java.io.*;
import java.util.*;
 
public class Prac5 {
 
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
    public static String wordSortUsingMap(String str) throws IOException {
 
        int n = Integer.parseInt(str.substring(0,str.indexOf('\n')));
        String[] words = str.substring(str.indexOf('\n')+1).split("[\n]");
        Map<Integer,List<String>> map = new LinkedHashMap<>();
        for(String s : words)
        {
            if(!map.containsKey(s.length())) map.put(s.length(), new LinkedList<>());
            if(!map.get(s.length()).contains(s)) map.get(s.length()).add(s);
        }
        // 키값을 정렬
        Integer[] keys = map.keySet().toArray(new Integer[]{});
        Arrays.sort(keys);
 
        // 리스트를 정렬
        for(int a :keys)
        {
            if(map.get(a).size()==1) continue;
            map.get(a).sort(null);
        }
 
        // 각 리스트에 있는 키 값과 value 값을 문자열로 반환
        StringBuffer stringBuffer = new StringBuffer("");
        List<String> arr;
        for(int a :keys)
        {
            arr = map.get(a);
            for(int i = 0 ; i < arr.size() ; i++) stringBuffer.append(arr.get(i)+"\n");
        }
        return stringBuffer.toString();
    }
 
    public static String wordSortUsingList(String str) throws IOException {
 
        int n = Integer.parseInt(str.substring(0,str.indexOf('\n')));
        String[] words = str.substring(str.indexOf('\n')+1).split("[\n]");
        List<List<Object>> coverlist = new LinkedList<>();
        List<Object> tmpList;
 
        for(String s : words)
        {
            tmpList = new LinkedList<>();
            tmpList.add(s.length());
            tmpList.add(s);
            if(!coverlist.contains(tmpList)) coverlist.add(tmpList);
        }
 
        coverlist.sort(new Comparator<List<Object>>() {
            @Override
            public int compare(List<Object> o1, List<Object> o2) {
                int result = Integer.signum((int)o1.get(0) - (int)o2.get(0));
                return result != 0 ? result : String.valueOf(o1.get(1)).compareTo(String.valueOf(o2.get(1)));
            }
        });
 
        StringBuffer stringBuffer = new StringBuffer("");
        for(int i = 0 ; i < coverlist.size() ; i++) {stringBuffer.append(String.valueOf(coverlist.get(i).get(1))+"\n");}
        return stringBuffer.toString();
    }
 
    public static void main(String args[]) throws IOException {
        String ranStr = prac.Prac2.makerandom(20000);
        long before, after;
 
        before = System.currentTimeMillis();
        wordSortUsingMap(ranStr);
        after = System.currentTimeMillis();
        bw.write("\n"+(after-before)/1000.0 + "sec");
 
        before = System.currentTimeMillis();
        wordSortUsingList(ranStr);
        after = System.currentTimeMillis();
        bw.write("\n"+(after-before)/1000.0 + "sec");
 
        bw.flush();
        bw.close();
    }
}

 테스트 코드는 위와 같고 그 결과는 다음과 같다.

거의 7배 가까이 차이가 나는 것을 볼 수 있다. 내가 잘못한 건지는 몰라도 sort메소드에 compare메소드를 오버라이드해서 정렬하는 방식은 조금 느리다는 것을 확인할 수 있었다.

 

물론 주요한 시간의 차이는 처음 값을 입력받을 때 중복값을 검사하는 과정에서 발생한다는 것을 감안해도 좀 심한 차이인 것 같다.

 

만약에 처음 중복값을 검사하지 않는다면 어떻게 될까해서 돌려보았더니 결과는 다음과 같았다.

여전히 7배 가까이 차이가 나는 것을 확인할 수 있었다.

---

소스코드

import java.io.*;
import java.util.*;
 
public class Main
{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
    public static String wordSort() throws IOException {
 
        int n = Integer.parseInt(br.readLine());
        Map<Integer,List<String>> map = new LinkedHashMap<>();
        String s;
        for(int i = 0 ; i < n ; i++)
        {
            s = br.readLine();
            if(!map.containsKey(s.length())) map.put(s.length(), new LinkedList<>());
            if(!map.get(s.length()).contains(s)) map.get(s.length()).add(s);
        }
        // 키값을 정렬
        Integer[] keys = map.keySet().toArray(new Integer[]{});
        Arrays.sort(keys);
 
        // 중복된 리스트를 정렬
        for(int a :keys)
        {
            if(map.get(a).size()==1) continue;
            map.get(a).sort(null);
        }
 
        // 각 리스트에 있는 키 값과 value 값을 문자열로 반환
        StringBuffer stringBuffer = new StringBuffer("");
        List<String> arr;
        for(int a :keys)
        {
            arr = map.get(a);
            for(int i = 0 ; i < arr.size() ; i++) stringBuffer.append(arr.get(i)+"\n");
        }
        return stringBuffer.toString();
    }
 
    public static void main(String args[]) throws IOException {
        bw.write(wordSort()+"");
        bw.flush();
        bw.close();
    }
}

---

느낀점

 

일단 좋아보이는 코드가 진짜 다 좋은건 아니구나라는 것을 느꼈다.