[BOJ 길라잡이/Java] 2일차 #2751 수 정렬하기 2

#2750 수 정렬하기와 비슷한 문제다.

https://gusdkstudyhard.tistory.com/221

사실상 같은 문제긴 한데, 입력값의 범위가 훨씬 커졌다.

N도 (1 <= N <= 1,000,000)의 범위를 가지고 주어지는 수도 1,000,000보다 작거나 같은 정수이다.

 

만약 선택 정렬로 문제를 풀게 되면

O(N^2)라서 10^12 -> 시간 제한 2초를 훌쩍 넘게 된다.

 

 

수 정렬하기 문제에서 풀었던 방법대로

int 배열을 만들어 Arrays.sort를 하고

StringBuilder를 사용해 한 번에 출력했다.

 

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

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());
        }

        Arrays.sort(arr);
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < N; i++) {
            sb.append(arr[i]);
            if(i != N - 1) {
                sb.append("\n");
            }
        }

        System.out.println(sb.toString());
    }
}

 

계수 정렬을 사용하는 방법도 O(N)으로 매우 빠르고,

boolean 타입 배열이 메모리 사용량이 매우 작아 공간 복잡도 문제도 없다고 한다.