BOJ 10989 수 정렬하기 3

1 개요

BOJ 10989 수 정렬하기 3

• 백준 온라인 저지 10989번 문제
• BOJ 13단계

• 카운팅 정렬(Counting Sort) 혹은 기수 정렬(Radix Sort)를 사용해 봅니다
• 알고리즘 분류: 정렬

2 C++

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
    int N;
    cin >> N;
    int a[10001] = {0};
    int i, j;
    for(i=0; i<N; i++) {
        cin >> j;
        a[j]++;
    }
	for(i=1; i<10001; i++) {
        for(j=0; j<a[i]; j++) {
            cout << i << '\n';
        }
    }
}

3 Java

기수정렬

import java.io.IOException;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
	static void count_sort(int arr[], int exp) {
		int size = arr.length;
		int output[] = new int[size];
		int count[] = new int[10];
		int i, index;
		for(i=0; i<size; i++) count[ (arr[i]/exp)%10 ]++;
		for(i=1; i<10; i++) count[i] += count[i-1];
		for(i=size-1; i>-1; i--) {
			index = arr[i]/exp;
			output[count[index%10]-1] = arr[i];
			count[index%10]--;
		}
		for(i=0; i<size; i++) arr[i] = output[i];
	}
	static void radix_sort(int arr[]) {
		int max = arr[0];
		for(int i:arr) if(max<i)max=i;
		for(int exp=1; max/exp>0; exp*=10) count_sort(arr, exp);
	}
	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[n];
		for(int i=0; i<n; i++) arr[i] = Integer.parseInt(br.readLine());
		radix_sort(arr);
		for(int i=0; i<n; i++) bw.write( arr[i] + "\n" );			
		bw.flush();
	}
}

4 Python

MAX=10000
a = [0]*MAX
f = open(0)
f.readline()
for i in f:
    a[int(i)]+=1
for i in range(MAX):
    print("%s\n" % i*a[i], end="")