[백준 문제풀이] 2751번 수 정렬하기2(with. JAVA)

백준 2751번 바로가기

2750번 수 정렬하기 문제와 같은 유형의 문제이다.

유형은 같지만, 입력 값의 범위가 다르다.

• 2750번(수 정렬하기) → N(1 ≤ N ≤ 1,000), |정렬할 수| ≤ 1,000
• 2751번(수 정렬하기2) → N(1 ≤ N ≤ 1,000,000), |정렬할 수| ≤ 1,000,000

2751번 문제는 2750번 문제보다 수의 범위가 1000배 증가한 것을 볼 수 있다. 따라서 2750번에서 사용했던 Arrays.sort()를 이번 문제에서도 그대로 사용하면 시간 초과가 발생하게 된다. 따라서 Arrays.sort() 대신 Collections.sort()를 사용해주어야한다.

(Collections.sort()에 대해선 Arrays.sort()와 함께 추가적인 게시글을 작성 후 링크를 달아두어야겠다.)

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

public class P2751 {

	// 2750번 문제와의 차이 -> 데이터와 수의 범위 증가 
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int n = Integer.parseInt(br.readLine());
		ArrayList<Integer> arr = new ArrayList<>();
		
		for(int i = 0; i < n; i++)
			arr.add(Integer.parseInt(br.readLine()));
		
		// Arrays.sort(arr); 의 최악 시간 복잡도는 O(n^2)
		// 되도록 O(n)에 가깝게 정렬하기 위해 Collections.sort(arr); 사용
		Collections.sort(arr);
		
		for(int a : arr)
			sb.append(a).append('\n');
		
		System.out.println(sb);
	}

}