문제
오름차순으로 정렬하시오
(첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.)
문제분석
입력의 수의 범위가 많으므로, 일반적인 정렬은 선택하는데에 시간초과의 가능성이 존재한다
기수 정렬을 이용하여 (O(KN)), 메모리 사용을 주의하며 작성
기수정렬 방식
- 자릿수별로 Queue를 이용하여, 정렬하고 이후 정렬될 숫자의 최대 자릿수만큼 반복하며 정렬하는 방식
- 시간복잡도 : O(KN) , K는 최대 자릿수
정렬 수 : |
60 |
12 |
20 |
45 |
30 |
75 |
32 |
88 |
99 |
30 20 60 |
|
32 12 |
|
|
75 45 |
|
|
88 |
99 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
일의 자리 정렬 : |
60 |
20 |
30 |
12 |
32 |
45 |
75 |
88 |
99 |
|
12 |
20 |
32 30 |
45 |
|
60 |
75 |
88 |
99 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
십의 자리 정렬 : |
12 |
20 |
30 |
32 |
45 |
60 |
75 |
88 |
99 |
- 일의 자릿수 끝났을 때 -> 일의자리수 정렬이 되있음 (따라서, 60 - 20 - 30 은 일의자리만 비교했기에, 정렬이 되지 않은상태로 저장)
- 십의 자릿수 끝났을 때 -> 십의자리 + 일의자리 정렬이 되있음
- 백의 자리수 끝났을 때 -> 백의자리 + 십의자리 + 일의자리 정렬이 되있음
기수정렬 구현
- 문제에서 숫자의 최대크기를 제한했으므로, 메모리를 해당 수 이하만큼 돌면 되므로 max_size를 설정하여 기수정렬을 풀이하면된다.
- 초기) getMax() 구현하여, 배열에서 최대값을 찾고 해당 자릿수만큼 반복하게 하였으나, 백준 테스트에 통과를 하지 못함..
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class App {
public static void radixSort(int[] arr, int max_size){
int[] output = new int[arr.length];
int exp = 1;
int count = 0;
while(count != max_size){
int[] sumArray = new int[10];
//자릿수에 맞춰서 저장
for(int i = 0; i< arr.length; i++){
sumArray[(arr[i]/exp)%10]++;
}
//합 배열 구하기
for(int i = 1; i<10; i++){
sumArray[i] += sumArray[i-1];
}
// output에 저장하는 인덱스가 해당 범위의 끝부터 저장하기에 큰수부터 넣어야한다 (그래서 반복문을 arr.length-1부터)
for(int i = arr.length-1; i >= 0 ; i--){
int digit = (arr[i]/exp)%10;
output[sumArray[digit] - 1] = arr[i];
sumArray[digit]--;
}
for(int i = 0; i<arr.length; i++){
arr[i] = output[i];
}
exp = exp*10;
count++;
}
}
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int arr_size = Integer.parseInt(bf.readLine());
int[] arr = new int[arr_size];
for(int i =0; i< arr_size; i++){
arr[i] = Integer.parseInt(bf.readLine());
}
bf.close();
radixSort(arr,5);
for (int i : arr) {
bw.write(i +"\n");
}
bw.flush();
bw.close();
}
}