백준 10989 수 정렬하기3 java 풀이

문제

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

입력

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

출력

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

 

나의 풀이

 카운터 정렬을 사용하라는 문제 설명이 있었기 때문에 진정한? 카운터 정렬로 먼저 코드를 작성했다. (코드2) 카운터 정렬의 특성한 (1, 0, 10000, 1, 2) 와 같이 입력한 숫자중에 공백이 넓은 경우 효율성이 떨어지기 때문에 코드2와 같이 작성하는 것이 일반적이다 라고 학습했었다. 결과적으론 테스트는 통과 되었는데 주어진 문제에서는 그냥 더 단순한 코드로 실행이 가능할 것 같아서 코드1도 작성해보았다. 

 

코드1

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

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 num = Integer.parseInt(br.readLine());
        int[] countArr = new int[10001];
        
        for(int i=0; i<num; i++) {
            countArr[Integer.parseInt(br.readLine())]++;
        }
        
        for(int i=1; i<countArr.length; i++) {
            int temp = countArr[i];
            while(temp>0) {
                bw.write(i+"\n");
                temp--;
            }
        }
        
        
        bw.flush();
    }
}

코드2

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

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 num = Integer.parseInt(br.readLine());
        int[] arr = new int[num+1];
        int[] ansArr = new int[num+1];
        int[] countArr = new int[10001];
        
        
        for(int i=1; i<=num; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        for(int n : arr) {
            countArr[n]++;
        }
        for(int i=1; i<10000; i++) {
            countArr[i+1] += countArr[i];
        }
        
        
        for(int i=num; i>=1; i--) {
            ansArr[countArr[arr[i]]] = arr[i];
            countArr[arr[i]]--;
        }
        
        for(int i=1; i<=num; i++) {
            bw.write(ansArr[i]+"\n");
        }
        
        
        bw.flush();
    }
}