ATM

백준 11399번 : ATM

• 처음엔 매우 쉽다고 느껴져서 문제를 바로 풀기 시작했다.

import java.util.Arrays;
import java.util.Scanner;

public class ATM {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);


        int N = sc.nextInt();

        int arr[] = new int[N];

        int sum = 0;
        int prev = 0;


        for (int i =0; i<N;i++){
            arr[i] = sc.nextInt();

        }

        Arrays.sort(arr);

/*        for (int i =0; i<N;i++){

            for (int j =0; j<=i;j++){
                sum += arr[j];

            }

        }*/

        for(int i = 0; i < N; i++) {
            // 이전까지의 대기시간과 현재 사람이 걸리는 시간을 더해준다.
            sum += prev + arr[i];

            // 이전까지의 누적합에 현재 걸리는 시간을 더해준다.
            prev += arr[i];
        }


        System.out.println(sum);


    }

}

• ArraysSort 를 이용해서 간단하게 풀었고 시간의 합을 구하는 방법을 여러가지 방법으로 구현해봤다.

CountingSort

• 하지만 이 문제는 CountingSort 알고리즘을 이용하여 해결할수도 있다.

Counting Sort는 시간복잡도가 O(n)으로 엄청난 성능을 보여주는 알고리즘 중 하나이다.

빠르다는 퀵 정렬, 힙 정렬, 합병 정렬등이 평균 O(nlogn) 인것에 비하면 확실히 빠르다.

이전 코드에는 index의 수를 비교하여 오름차순으로 정렬하여 최선 값을 구했다면, 카운팅 정렬에서는 배열을 순회하면서 'arr' 배열에 각 숫자가 등장하는 횟수를 카운트 하는 것.

입력예시

5
3 1 4 3 2

arr[1] = 1, arr[2] = 1, arr[3] = 2, arr[4] = 1

이런식..

import java.util.Scanner;

public class ATM_CountSort {
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int N = in.nextInt();


        // 입력의 범위는 1 ~ 1000이므로 1001개의 index를 둔다.
        int[] arr = new int[1001];

        // Counting Sort
        while (N-- > 0) {
            arr[in.nextInt()]++;
        }

        int prev = 0;	// 이전까지의 대기시간 누적합
        int sum = 0;	// 사람별 대기시간 총합

        for (int i = 0; i < 1001; i++) {

            // 해당 i index가 0이 될 때 까지 반복
            while (arr[i]-- > 0) { //arr[i]--; arr[i] > 0; 이 두 가지를 합쳐놓은 것
                // 이전까지의 대기시간과 현재 사람이 걸리는 시간을 더해준다.
                sum += (i + prev);

                // 이전까지의 누적합에 현재 걸리는 시간을 더해준다.
                prev += i;
            }
        }
        System.out.println(sum);
    }

}

결과

확실히 카운팅 정렬 알고리즘을 이용한 코드가 더 빠른것을 알수 있다.