[백준] 2751 수 정렬하기2 (후기)

문제

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

정답 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class bj_2751 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		
		ArrayList<Integer> arr_int = new ArrayList<Integer>();
		
		StringBuilder sb = new StringBuilder();
		
		for(int i = 0; i < num; i++) {
			
			int number = sc.nextInt();
			arr_int.add(number);
		}
		
		Collections.sort(arr_int);
		
		for(int i : arr_int) {
			sb.append(i + "\n");
		}
		
		System.out.print(sb.toString());
	}
}

풀이 방법

1.입력 받아 ArrayList에 저장
2.Collections.sort() 오름차순 정렬
3.StringBuilder() 출력

후기

이 문제를 풀면서 2가지의 의문점을 가졌다.
첫 번째 왜 Arrays. sort() 대신 왜 Collections. sort() 함수를 사용해야 하는가?
두 번 째 왜 String Builder() 함수를 이용하여 출력을 해야 하는가

이러한 의문점을 가지고 자료를 찾아보았다.

1.2750수 정렬하기 1 문제에서는 N의 범위가 1부터 1000까지이기 때문에 Arrays.sort()를 사용해도 문제를 풀 수 있지만
2751수 정렬하기 2 문제에서는
N의 범위가 1부터 1000000까지이기 때문에 1,000,000개의 데이터를 입력하고 정렬할 땐 시간제한을 초과할 수 있기 때문이다. 또한 Arrays.sort()의 시간복잡도는 최악의 경우 (O^2)이고
Collections.sort()는 최악과 보통도 O(nlog(n))의 시간복잡도를 가지기 때문에 Arrays.sort() 대신 Collections.sort()를 사용해야 한다는 생각이 들었다.

2. 왜 string builder()를 사용해야 하는가?
솔직히 이 문제를 풀 때 Collections.sort() 정렬 후 ArrayList 데이터를 출력하고 제출했는데 틀렸다고 나왔다. 내가 문제를 잘못 이해했나 싶었는데 알고 보니 메모리 성능과 시간의 이유로 StringBuilder를 사용해서 한꺼번에 출력을 해야 하는 문제였기 때문에 StringBuidler()를 왜 이용해야 하는지 알게 되었다.

느낀 점

정렬 문제는 N의 범위도 잘 확인해야 하고 시간복잡도가 왜 중요한지 알게 된 문제였다.