배열_백준_10989_수 정렬하기 3

10989번: 수 정렬하기 3

파악

그냥 정렬하면 된다. 근데 소팅 메소드나 삽입 정렬 같은거 쓰면 O($n^2$)인데 숫자가 $10^7$씩이나 들어와서 쉽지않다.

접근

N개의 숫자와 자연수([1, 10000])의 범위가 들어오는데 이 자연수는 $10^4$밖에 안돼서 이걸 써야할듯

어차피 자연수만 들어오고 index도 자연수니까 카운트배열을 사용하면서 카운트배열의 인덱스에 해당하는 숫자가 0이 아니라면(존재한다면) index 순서대로 정렬해주면 되지 않을까

주의해야할 점이 이 방법은 자연수로 10만개 정도가 들어오면 메모리가 넘쳐서 쓰기 힘들 뿐더러 숫자가 아니라면 쓰기 힘들다.

만약 음수가 있다면 0에는 0은 -100이고 200은 100으로 사용할 수도 있다.

import java.util.Scanner;

class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] cnt = new int[10001];

        for (int i = 0; i < N; i++) {
            cnt[sc.nextInt()]++;
        }

        for (int i = 1; i <= 10000; i++) {
            while (cnt[i]-- > 0) {
                System.out.println(i);
            }
        }
    }
}

이렇게하면 시간초과가 뜨는데.. 사실 시간 복잡도는 O(n)으로 넘치지 않는다. 근데 지금 입출력 숫자가 굉장히 많은 경우에는 입출력 자체가 문제가 될 수 있다.

스캐너 대신에 BufferedReader나 BufferedWriter를 써보자

풀이

import java.io.*;

class Main {
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader((new InputStreamReader(System.in)));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[] cnt = new int[10001];

        for (int i = 0; i < N; i++) {
            cnt[Integer.parseInt(br.readLine())]++;
        }

        for (int i = 1; i <= 10000; i++) {
            while (cnt[i]-- > 0) {
                bw.write(i + "\\n");
            }
        }
        bw.flush();
    }
}