N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N;
static int[] input;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder result = new StringBuilder();
N = Integer.parseInt(br.readLine()); //숫자 개수(문제 제시된 값)
input = new int[N]; //입력받은 배열
for(int i = 0; i < N; i++) {
input[i] = Integer.parseInt(br.readLine());
}
radixSort(input);
for(int i : input)
result.append(i).append('\n');
System.out.print(result);
}
static void radixSort(int[] input) {
int[] bucket = new int[10]; //n자릿수가 몇 개 있는지 알려주는 합 배열
int[] output = new int[N]; //임시 정렬 배열
int now = 1; //현재 자릿수
int cnt;
while(now < 100000) {
Arrays.fill(bucket, 0);
Arrays.fill(output, 0); //0으로 초기화
for (int i = 0; i < N; i++) {
int num = input[i] % (now * 10) / now;
bucket[num] += 1;
}
for (int num = 1; num < 10; num++) { //1부터 9까지
bucket[num] += bucket[num - 1];
}
for (int i = N - 1; i >= 0; i--) {
int num = input[i] % (now * 10) / now;
int index = bucket[num] - 1;
output[index] = input[i];
bucket[num]--;
}
for(int i = 0; i < N; i++)
input[i] = output[i];
now *= 10;
}
}
}
잘 보고 갑니다👍