백준 2751 - 수 정렬하기 2 (Java, 빠른 입출력)

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

전체 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 빠른 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        // O(N log N) 정렬
        Arrays.sort(arr);

        // 빠른 출력
        StringBuilder sb = new StringBuilder();
        for(int num : arr) {
            sb.append(num).append("\n");
        }

        System.out.print(sb);
    }
}

 

코드 설명

입력

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());

• BufferedReader는 Scanner보다 훨씬 빠른 입력 방식이다.
• readLine()으로 한 줄을 읽고, Integer.parseInt()로 숫자로 변환한다.

---

정렬

Arrays.sort(arr);

• Java의 기본 정렬 알고리즘은 Dual-Pivot QuickSort (Primitive type 기준)로 시간 복잡도 O(N log N)

---

출력

StringBuilder sb = new StringBuilder();
for(int num : arr) {
    sb.append(num).append("\n");
}
System.out.print(sb);

• System.out.println을 N번 호출하면 시간 초과가 날 수 있으므로 StringBuilder로 모든 결과를 한 번에 출력한다.

---

시간 복잡도

• 입력: O(N)
• 정렬: O(N log N)
• 출력: O(N)
• 총 시간 복잡도: O(N log N)