[백준/자바] 10989 - 수 정렬하기 3

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

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

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

        for(int i=0; i<n; i++) arr[i] = Integer.parseInt(br.readLine());
        Arrays.sort(arr);

        for(int i : arr) sb.append(i).append("\n");

        System.out.println(sb);

        br.close();
    }
}

Arrays.sort()를 이용한 풀이

(통과는 했으나 시간이 아슬아슬했다.)

(StringBuilder 대신 System.out.print()를 사용했더니 시간 초과가 떴다.)

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

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[] array = new int[n];
        
        int[] counting = new int[10001];
        
        int[] result = new int[n];

        for(int i=0; i<n; i++) counting[Integer.parseInt(br.readLine())]++;
        
        for(int i=0; i<counting.length;i++) {
        	int count = counting[i];
        	if(count !=0) bw.write((i+"\n").repeat(count));
        }

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

각각의 수가 10000보다 작거나 같다는 점을 이용하여 counting[]을 사용한 풀이

---

import java.io.*;

public class Main {

    private static int[] arr;

    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());

        arr = new int[N];

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

        radixSort(arr, 5);

        for (int num : arr) bw.write(num + "\n");

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

    private static void radixSort(int[] arr, int max) {
        int[] result = new int[arr.length];
        
        int target = 1;
        int count = 0;
        
        while (count != max) {
            int[] bucket = new int[10];
            for (int n : arr)
                bucket[(n / target) % 10]++;
            
            for (int i = 1; i < 10; i++)
                bucket[i] += bucket[i - 1];
            
            for (int i = arr.length - 1; i >= 0; i--) {
                result[bucket[(arr[i] / target % 10)] -1] = arr[i];
                bucket[(arr[i] / target) % 10]--;
            }
            
            for (int i = 0; i < arr.length; i++)
                arr[i] = result[i];
            
            target *= 10;
            count++;
        }
    }
}

기수 정렬을 이용한 풀이