[JAVA] 백준 - 2751번(수 정렬하기2)

문제를 보고 '너무 간단하잖아? 배열 만들어서 넣고 sort함수 써서 정렬하고 출력하면 되겠네' 라고 생각하고 정답 비율을 보았는데 흠칫했다. 약간의 불안을 안고 코딩을 시작했다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	    
	    int n = Integer.parseInt(br.readLine());
	    int[] arr = new int[n];
	    
	    for(int i=0; i<arr.length; i++) {
	    	arr[i] = Integer.parseInt(br.readLine());
	    }
	    Arrays.sort(arr);
	    
	    for(int i=0; i<arr.length; i++) {
	    	bw.write(arr[i] + "\n");
	    	bw.flush();
	    }
	}
}

이것이 나의 코드였다. 결과는 당연히(?) 시간초과... 아니 왜?! sort함수 말고 다른 방법이 있단 말인가?

그래서 찾아보았다. 당연히 다른 방법이 있었다. Collections.sort 였다. 하지만 ArrayList를 사용해야했다. 그것은 나에게 문제가 되지 않았다 바로 수정하였다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
		ArrayList<Integer> list = new ArrayList<Integer>();

		for(int i=0; i<n; i++) {
			list.add(Integer.parseInt(br.readLine()));
		}
		Collections.sort(list);

		for(int i=0; i<n; i++) {
			bw.write(list.get(i) + "\n");
			bw.flush();
		}
	}
}

결과는 역시(?) 시간초과... 대체 왜이러는 걸까... 다른사람들은 Collections.sort 함수 사용해서 정답처리되었다는데 ...

다시한번 살펴보았다. StringBuilder를 사용하는 것을 볼 수 있었다. 사실 난 StringBuilder를 잘 쓰지 않고 있었다. 그래서 생각해내지 못했던 것 같다. 조만간 StringBuilder에 대해 자세한 설명을 포스팅 해보겠다.

 

마지막으로 StringBuilder를 사용한 나의 코드이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine());
		ArrayList<Integer> list = new ArrayList<Integer>();

		for(int i=0; i<n; i++) {
			list.add(Integer.parseInt(br.readLine()));
		}
		Collections.sort(list); // 오름차순으로 정렬

		for(int e : list) { //for each문 사용. 
			sb.append(e).append("\n"); //ArrayList 각 요소 하나하나 StringBuilder 객체 sb에 담고 개행처리
		}
		System.out.println(sb); //sb에 담은 문자열 모두 출력
	}
}

 

* Collections.sort() 은 Timsort이다. Timsort 의 경우 반복 합병 및 삽입정렬 알고리즘을 사용하는데, 이렇게 두 가지가 섞여있는 정렬 알고리즘을 hybrid stable sorting algorithm 이라고 하는데, 합병정렬(Merge Sort)의 경우 최선, 최악 모두 O(nlogn) 을 보장하고. 삽입정렬(Inser tsort)의 경우 최선의 경우는 O(n) , 최악의 경우는 O(n2) 이다.

​ 즉, 합병정렬의 최악의 경우와 삽입정렬의 최선의 경우를 짬뽕한 알고리즘이 Timsort 라는 것이다. 실제로 파이썬이나 기타 정렬 알고리즘에서 가장 많이 쓰이는 알고리즘이기도 하다.

시간복잡도 O(n) ~ O(nlogn) 을 보장한다는 장점이 있다고 한다.