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

실버 V

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

---

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

---

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

---

접근 방법

Collections.sort()를 이용하여 오름차순으로 정렬하고, StringBuilder를 이용하여 출력한다.

---

코드

package bj_2751;

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


public class bj_2751 {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		 int num = Integer.parseInt(br.readLine());
		 StringBuilder sb = new StringBuilder();
			
		 //리스트에 숫자넣기
		 ArrayList<Integer> list = new ArrayList<>();
		 
		 for(int i = 0; i < num; i++)
			 list.add(Integer.parseInt(br.readLine()));

		 // 오름차순 정렬
		 Collections.sort(list);
			
		 // 결과 출력
		 for(int value : list)
			 sb.append(value).append('\n');
		    
		 System.out.println(sb);
	}

}

---

NOTE

처음에 Arrays.sort()으로 오름차순으로 정렬한 뒤 System.out.println()로 출력하였는데 시간초과가 났다.

그 이유는 Arrays.sort()는 퀵 정렬 알고리즘을 사용하는데 최악인 경우의 시간복잡도는 O(n2)이다.

반면, Collections.sort()는 Timesort 정렬 알고리즘을 사용한다. 이 정렬은 최악인 경우의 시간복잡도도 O(nlogn)이다.

이 정렬을 사용할 때 주의할 점은 StringBuilder를 사용하여 출력해야 한다는 것이다.