수 정렬하기 3(10989)

수의 범위가 작다면 카운팅 정렬을 사용하여 더욱 빠르게 정렬할 수 있습니다.

문제

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

• 시간제한 3초

• 메모리제한8MB

수의 범위가 작다면 카운팅 정렬을 사용하여 더욱 빠르게 정렬할 수 있습니다.

메모리가 제한되었다는 것은... 무슨뜻이냐 => 출력을 줄여라? 이걸 줄일려고 System.out.println() 을 안쓰고 StringBuilder를 썼는데 이건안되는거같고

그러면 다음 방법이 BufferedWriter? 이거써도 초과네?

뭐지... 카운팅 정렬이란 무엇인가 찾아보자

카운팅 정렬이란 일일이 비교하지 않고 몇 개인지 센 다음에 정렬하는 방법이라네

카운터정렬은

위에서 말했지만 수의범위가 작을때 사용하면 좋을 정렬방법인거같다

따로 입력을 받은 숫자들을 배열에 넣어서 비교하는과정이 아니라

최대 범위까지의 숫자로 이루어진 배열을 만들고

입력받은 숫자위치의 숫자의 카운팅을 해줌

-- 여기까지하면 어떤 숫자가 들어왔는지 배열의 위치에 저장해두었으며 몇번 들어와있는지 저장되어있음 그리고 배열의 순서대로니까 정렬은 이미 되어있다

이제 출력하는 과정인데, 출력은 간단하다

카운팅이 되어있을 테니까 0보다 클때 카운팅을 줄여가면서 순서를 순서대로 출력

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력

10
5
2
3
1
4
2
3
5
1
7

예제 출력

1
1
2
2
3
3
4
5
5
7

풀이

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

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

        for(int i=0; i<10001; i++){
            while(arr[i]>0){
                bw.write(Integer.toString(i));
                bw.newLine();
                arr[i]--;
            }
        }

        bw.flush();
        bw.close();
    }


}

백준