[JAVA] 백준 11399 : ATM

11399번: ATM

 

정렬 알고리즘 중 Counting Sort Algorithm을 이용했다.

counting sort는 저장공간을 많이 씀으로써 시간을 단축시키는 정렬 알고리즘이다.

n개의 입력 원소가 0 이상 k 이하인 정수들일 때, 오름차순 배열하는데 걸리는 시간은 O(max{n, k})이다.

 

1. arr은 입력 배열, max는 걸리는 시간의 최댓값, rs는 오름차순으로 재배열한 결과배열이다.

2. count 배열에 인덱스 0부터 max까지 0개의 개수, 1개의 개수 ... max개의 개수를 저장하고, 이를 누적시켜 저장한다.

3. count[i] > count[i - 1]일 때, i는 count[i - 1]번째부터 count[i] - 1번째까지 위치하게 된다.

 

예제의 경우,

arr : 3  1  4  3  2

count : 0  1  1  2  1  ->  0  1  2  4  5 (누적 저장)

     i = 1 : 0 ~ 0번째

     i = 2 : 1 ~ 1번째

     i = 3 : 2 ~ 3번째

     i = 4 : 4 ~ 4번째에 들어가게 됨

rs : 1  2  3  3  4

이렇게 진행된다.

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

public class Main {
    static int num, max;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		num = Integer.parseInt(br.readLine());
		int[] arr = new int[num];
		max = 0;
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < num; i++) {
			int n = Integer.parseInt(st.nextToken());
			if (n > max)
				max = n;
			arr[i] = n;
		}
		int[] rs = new int[num];
		countingSort(arr, rs);
		int sum = 0;
		for (int i = 1; i < num; i++) {
			rs[i] += rs[i - 1];
		}
		for (int i = 0; i < num; i++) {
			sum += rs[i];
		}
		System.out.println(sum);

	}

	public static void countingSort(int[] arr, int[] rs) {
		int[] count = new int[max + 1];
		for (int i = 0; i <= max; i++) {
			count[i] = 0;
		}
		for (int j = 0; j < num; j++) {
			count[arr[j]] += 1;
		}
		for (int i = 1; i <= max; i++) {
			count[i] += count[i - 1]; // 누적
		}
		for (int j = num - 1; j >= 0; j--) {
			count[arr[j]] -= 1;
			rs[count[arr[j]]] = arr[j];
		}

	}
}