[BOJ] 백준 10989 수 정렬하기 3

출처: https://www.acmicpc.net/problem/10989

 Input 
10
5
2
3
1
4
2
3
5
1
7

 Output 

1
1
2
2
3
3
4
5
5
7　

N이 크기 때문에 제한시간을 만족시키기 어렵다.

정렬기법을 사용하지 않고 배열 원소 index 이용

중복되어 입력될 수 있으므로 원소값은 중복 개수 할당.

 

ex) arr[5] = 3 / arr[8] = 2 라면 출력결과는 다음과 같다.

▶ 5 5 5 8 8

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        // 1 ≤ N ≤ 10,000,000
        int N = Integer.parseInt(br.readLine());
         
        // 입력되는 숫자 <= 10,000 같은 자연수
        // 1 <= arr[] = 10000
        int[] arr = new int[10001];
         
        for (int i = 0; i < N; i++) {
            // 각 배열에 해당 숫자가 몇번 중독되었는지도 체크한다.
            arr[Integer.parseInt(br.readLine())] ++;
        }
         
         
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // 이제 각 원소에 저장된 숫자만큼 중복해서 숫자를 출력하면 결국 오름차순으로 출력하게 된다.
        for (int i=1; i <= 10000; i++) {
            if (arr[i] > 0) {
                // 하나이상 입력되었다면 그 입력된 만큼 출력
                for (int j = 0; j < arr[i]; j++) {
                    bw.write(Integer.toString(i) + "\n");
                }
            }
        }
        bw.flush();
        br.close();
        bw.close();
    }
}