[백준 온라인 저지] 1181. 단어 정렬

1. 입력

- 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000)

- 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

 

2. 출력

- 다음 조건에 따라 정렬하여 단어들을 출력한다.

// 길이가 짧은 것부터 출력한다.

// 길이가 같으면 사전 순으로 출력한다.

// 중복된 단어는 하나만 남기고 제거해야 한다.

 

3. 예제

 

4. 코드

1) 첫 코드

import java.util.*;
import java.io.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.valueOf(br.readLine());
        String[] word = new String[n];
        for(int i=0 ; i<n ; i++)
        	word[i] = br.readLine();
        String temp;
        for(int i=0 ; i<word.length-1 ; i++) {
        	int j = i; // 정렬하고자 하는 요소의 위치. i-1번째 까지는 정렬이 된 상태
        	while(j>=0 && compare(word[j],word[j+1])) { // i번째 요소의 적절한 위치를 찾아간다.
        		   temp = word[j];
        		   word[j] = word[j+1];
        		   word[j+1] = temp; j--; // 적절한 위치를 찾을 때까지 인덱스를 감소시킨다. 
        	}
        }
        for(int i=0 ; i<n ; i++) {
        	if(i>0 && word[i].equals(word[i-1])) continue;
        	bw.write(word[i]+"\n");
        }        	
        bw.flush(); bw.close();
    }
    
    static boolean compare(String s1, String s2) { // true: 더 뒤로 가야하는 단어
    	if(s1.length()>s2.length())
    		return true;
    	else if(s1.length()==s2.length())
    		return s1.compareTo(s2)>0;
    	else
    		return false;
    }
}

 

2) 시간이 훨씬 적게 걸린 코드들의 공통점 (1) - 내가 쓴 compare() 대신 Arrays.sort() 이용

Arrays.sort(word, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                if(s1.length() == s2.length()) {  //사전 순 정렬
                    return s1.compareTo(s2);
                } else {
                    return s1.length() - s2.length();
                }
            }
        });
        
// 위 Comparator를 람다식으로 표현
Arrays.sort(word, (e1, e2) ->{
			if(e1.length() == e2.length()) {
				return e1.compareTo(e2);
			}else {
				return e1.length() - e2.length();
			}
		});

 

3) 시간이 훨씬 적게 걸린 코드들의 공통점 (2) - word[0]은 먼저 출력하고 다음에 중복 제거 이용

// BufferedWriter 이용
bw.write(word[0]+"\n");
for(int i=1 ; i<n ; i++)
    if(!word[i].equals(word[i-1]))
        bw.write(word[i]+"\n");
        
// StringBuilder 이용
StringBuilder sb = new StringBuilder();
sb.append(word[0]).append("\n"); // '\n'도 상관없음
for(int i=1 ; i<n ; i++)
    if(!word[i].equals(word[i-1]))
        sb.append(word[i]).append("\n");