[백준] 10989 : 수 정렬하기 3

🙋🏻‍♀️기수정렬 이용! (구간합 사용)

문제분석

N의 최대가 10,000,000으로 매우 크기때문에 O(nlogn)보다 빠른 알고리즘이 필요하다.
기수정렬의 시간복잡도는 O(kn)인데, 숫자의 크기의 최대가 10,000이므로 5자리라서 O(5*10^7)이다. 따라서 3초안에 해결될것으로 보인다.

슈도코드

N입력받기
A선언 (정렬할 배열)
for(N만큼 반복) {
	A 배열 저장
}
기수정렬 함수 수행
정렬된 A배열 출력

//기수 정렬 함수 구현
//변수 선언 부

제출코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.LinkedList;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;

public class Main {
public static int[] A;
public static long result;
	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<A.length; i++) {
				bucket[(A[i]/jarisu) % 10]++;
			}
			
			for(int i=1; i<10; i++) {
				bucket[i] += bucket[i-1];
			}
			
			for(int i= A.length-1; i>= 0; 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++;
		}
	}
}

주의사항

이건 사실 주의사항보다 특이사항인데, 모든 값을 배열에 저장하는 기수정렬의 원래로직인 큐(LinkedLisr)를 이용해서 구현하면 메모리초과가난다.
이 문제는 특히 메모리초과에 취약한 문제이다.
LinkedList를 이용했을 때 최악의 경우 사용되는 메모리가 10^7*4byte 인데, 메모리 제한이 8MB로 8*10^6byte이므로 메모리제한을 훨씬 초과한다.

공부한 사항

• 기수정렬시, 자릿수가 서로 다른 경우 자릿수가 적은 수 앞에 0이 채워져있다고 생각!
• 자릿수 구하기
  : 주어진 수 / 구하고싶은 자리수(1,10,100...) % 10