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

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

---

문제

---

풀이

 

import java.util.*;

public class Main {

	public static void main(String[] args) {

		Scanner kb = new Scanner(System.in);
		StringBuilder pr = new StringBuilder();
		int N = kb.nextInt();
		
		ArrayList<Integer> list = new ArrayList<>();
	
		for(int i = 0; i < N; i++) {
			list.add(kb.nextInt());
		}
		
		Collections.sort(list);

		for(Integer c : list) {
			pr.append(c).append("\n");
		}
		
		System.out.println(pr);
	}
}

가장 먼저 생각한 아이디어는 2가지는 TreeSet을 사용할지 Collections.sort 방식을 사용할지다. 

Arrays.sort() 를 사용하면 최악의 경우 시간 복잡도가 O(n^2)를 고려하여 사용하지 않았고, 합병정렬 방식인 Collections.sort 방식을 사용했다. 최악의 경우에도 O(nlogn)의 시간 복잡도를 가지기 때문이다.

 

출력 방식으로 StringBuilder을 사용한 것은 새로운 객체를 생성하는 것이 아닌, 기존의 객체에 더하는 방식으로 더욱 속도가 빠르기 때문이다.