백준 알고리즘 11399 ATM 문제

문제

이번 알고리즘 문제는 최소 ATM 사용시간을 구하는 문제이다. 

주어진 사람마다 ATM 사용시간이 주어진다. 이 사용시간에 따라 어떻게 사람이 서있을 때 빠르게 모두 ATM 을 사용할 수 있는지 구하는 문제이다.

각 사람마다 걸리는 시간을 모두 더해서 가장 최소의 시간이 나오게 하는 구현하는게 목표이다.

가장 빠르게 모두 인출이 끝나기 위해서는 사용시간이 가장 작은 사람 부터 큰 순서대로 서서 인출을 해야한다. 왜냐하면 뒤에 있는 사람이 인출하는데 걸리는 시간은 결국 앞사람이 사용한 시간의 누적값이기 때문이다. 

코드

소요시간 별로 오름차순으로 정렬한 후 에 합을 구하면 된다. 그러기 위해서 모든 데이터를 입력받고나서 가장 시간 복잡도가 낮은 퀵정렬을 사용하면하면 되지만 그냥 데이터가 삽입되는 순간에 삽입정렬을 사용하여 데이터를 정렬된 상태로 넣었다.

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
 
public class Main {
 
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
 
        // 사람 수
        int peopleCnt = sc.nextInt();
 
        // 사람 별 기다리는 시간
        List<Integer> waitTimes = new LinkedList<>();
 
        for (int cnt = 0; cnt < peopleCnt; cnt ++) {
            insertSort(waitTimes, sc.nextInt());
        }
 
        // 가장 적게 기다릴 수 있는 시간 구하기
        calMinWaitTimeSum(peopleCnt, waitTimes);
    }
 
    /**
     * 데이터를 정렬하면서 삽입
     * 
     * @param list
     * @param insertData
     */
    private static void insertSort(List<Integer> list, int insertData) {
        for (int index = 0; index < list.size(); index++) {
            if (list.get(index) > insertData) {
                list.add(index, insertData);
                return;
            }
        }
 
        list.add(insertData);
    }
 
    /**
     * 사람별 기다리는 최소 시간의 합
     *
     * @param peopleCnt
     * @param waitTimes
     */
    private static void calMinWaitTimeSum(int peopleCnt, List<Integer> waitTimes) {
        int timeSum = 0;
 
        for (int index = 0; index < waitTimes.size(); index++ ) {
            for (int subIndex = 0; subIndex <= index; subIndex++) {
                timeSum += waitTimes.get(subIndex);
            }
        }
 
        System.out.println(timeSum);
    }
 
 
}
 

자세한 코드는 git 참조
https://github.com/weduls/algorithm/blob/master/%EA%B7%B8%EB%A6%AC%EB%94%94%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/ATM/wedul/Main.java