(Java) 백준 2751번 - 수 정렬하기 2

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

문제

> N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

접근

수를 입력받아 배열에 저장 한 뒤 sort를 사용하여 정렬해 출력한다.

문제해결

> 수의 개수 N을 입력받고 N의 크기를 가지는 배열을 만든다.
> sort를 통해 배열 num을 오름차순 정렬해준다.
> Stringbuilder로 출력을 한꺼번에 모아 출력해준다.

코드

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

public class Main
{
    //2751번 수 정렬하기 2
    static int N;
    static int[] num;
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        num = new int[N];
        for(int i = 0; i < N; i++) num[i] = Integer.parseInt(br.readLine());
        Arrays.sort(num);

        StringBuilder sb = new StringBuilder();
        for(int a : num) sb.append(a).append('\n');

        System.out.print(sb);
    }
}

후기

브론즈 급인거같은데..
나처럼 sort가 아닌 카운팅 정렬이라는게 있다고 한다.
지금 처럼 +,- 합쳐서 범위가 2,000,001밖에 안되기 때문에 가능하다고 한다. 보통 합쳐서 10,000,000정도 까진 괜찮다고 한다.
그래서 이 입력받은 수를 인덱스로 boolean형 배열에 입력받은 수를 true로 저장해두고 나중에 이 배열을 순회하며 true인 인덱스만 출력해주면 된다고 한다. 그러면 시간복잡도가 O(N)만 나온다고 한다.
쇼킹하다.