탐욕법 알고리즘 예제(1). 백준 [11399] ATM

백준[11399] - ATM

대기 인원을 입력받고 각 인원들의 대기 시간을 최소한으로 만드는 문제이다.
생각해보면 간단한 문제이다. 
대기시간의 합을 최소한으로 만들기 위해서는 자신의 앞사람들의 인출하는데 필요한 시간이 적게 만들면 된다.
즉, 시간이 적게 걸리는 사람들을 우선으로 처리하면 된다. 

운영체제에서 배웠던 스케줄링 방식 중, SJF(Shortest Job First)방식을 떠올릴 수 있다. 

입력을 받을 때, 우선순위 큐를 이용하여 저장한 뒤 하나씩 out 시키며 배열에 저장한다.
그러면 시간이 적은 순서대로 배열에 저장 할 수 있다. 

그 후, 마지막 요소부터 자신 전까지의 요소를 모두 더해나가면 답을 구해낼 수 있다.

다음은 Java로 작성한 코드이다.

import java.util.PriorityQueue;
import java.util.Scanner;

public class ATM {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		
		int n = scan.nextInt();
		int[] wait = new int[n];
		
		//우선순위 큐
		PriorityQueue<Integer> people = new PriorityQueue<Integer>();
		
		//입력
		for (int i = 0; i < n; i++) {
			people.add(scan.nextInt());
		}
		
		//시간이 작은 순서로 poll
		for (int i = 0; i < n; i++) {
			wait[i] = people.poll();
		}
		
		//대기시간 총합 구하기
		int sum = 0;
		for (int i = n; i > 0; i--) {
			for (int j = 0; j < i; j++) {
				sum += wait[j];
			}
		}
		
		System.out.println(sum);
	}

}

요소를 더하면서 시간 복잡도를 O(n^2)로 작성하였다. 
하지만, 좀 더 고민해보면 충분히 줄일 수 있을 것 같다.