백준 10989 - 수 정렬하기 3

YongHyun·2023년 4월 17일

Java 백준 코딩테스트

백준, 프로그래머스 - 코딩테스트

목록 보기

22/43

문제

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

입력

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

출력

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

예제 입력 1

10
5
2
3
1
4
2
3
5
1
7

예제 출력 1

1
1
2
2
3
3
4
5
5
7

문제 풀이

처음 문제의 지문을 읽어봤을 때 N의 최댓값이 10,000,000 이라서 Arrays.sort( ) 메서드를 사용하여 푸는 문제인줄 알았다.

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

public class 수정렬하기3{

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

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

        Arrays.sort(A);

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < A.length; i++) {
            sb.append(A[i] + "\n");
        }
        System.out.println(sb);
    }
}

물론 맞게 문제를 풀었지만 시간에서 아슬아슬하게 통과했다는 것을 알았고 다른 방식으로 접근해야 한다는 것을 알게 되었다.

그러다가 이번 수 정렬하기 3 문제는 카운팅 정렬 알고리즘을 사용하면 쉽게 해결된다는 것을 검색을 통해 알게 되었다.

카운팅 정렬 알고리즘을 그림으로 쉽게 이해할 수 있는 사이트가 있어서 가져와 보았다.
https://www.cs.usfca.edu/~galles/visualization/CountingSort.html

일의 자리를 기준으로 먼저 배열에 삽입을 한 후에 점차 십의 자리, 백의 자리 ... 만의 자리까지 배열을 삽입하고 정렬하는 것이 문제의 핵심이다.

예제 입력 1 처럼 10개의 원소들을 가진 A 배열 [5, 2, 3, 1, 4, 2, 3, 5, 1, 7]과
현재 자릿수들의 분포를 합 배열의 형태로 알려주는 bucket 배열
임시 정렬을 위한 output 배열
자릿수를 표현하는 변수 jarisu

참고 블로그 : https://st-lab.tistory.com/104

import java.io.*;

public class 수정렬하기3{

    public static int[] A;

    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());
        A = new int[N];
        for(int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(br.readLine());
        }
        br.close();

        Radix_Sort(A, 5);
        for(int i = 0; i < N; i++) {
            bw.write(A[i] + "\n");
        }
        bw.flush();
        bw.close();

    }

    public static void Radix_Sort(int[] A, int max_size) {
        int[] output = new int[A.length];
        int jarisu = 1;
        int count = 0;

        while(count != max_size) {
            int[] bucket = new int[10];
            for(int i = 0; i < output.length; i++) {
                bucket[(A[i] / jarisu % 10)]++;
            }
            for(int i = 1; i < 10; i++) {
                bucket[i] += bucket[i - 1];
            }
            for(int i = 0; i < output.length; i++) {
                output[bucket[(A[i] / jarisu % 10)] - 1] = A[i];
                bucket[(A[i] / jarisu % 10)]--;
            }
            for(int i = 0; i < A.length; i++) {
                A[i] = output[i];
            }
            jarisu = jarisu * 10;
            count++;
        }
    }
}