백준 11399 - ATM (Java)

 

문제 개요

 

백준 - ATM

 

풀이

줄을 서는 순서에 따라 모든 사람들의 기다리는 시간의 총합이 달라질 때, 총합이 가장 적어질 때를 구해야 한다. 즉, 아무렇게나 줄을 설 수 있지만 전 인원의 웨이팅 시간의 합이 가장 적어지는 경우를 특정해야 하므로 그리디(탐욕)하게 접근해야 한다.

 

지문 속 예시대로 인출하는 데 걸리는 시간이 적은 순서대로 줄을 세웠을 경우가 우리가 특정하고자 하는 경우이다.

 

내가 생각한 로직의 순서는

 

1. 전체 사람들의 인출 시간을 입력받아 int형으로 변환한다.
2. 해당 데이터를 오름차순으로 정렬한다.
3. 반복문을 이용해서 각 사람이 기다리게 되는 수를 구한 후 더해준다.
   • 단순히 int형 변수인 sum을 하나 선언해서 sum을 반환하면 안 된다.
   • sum을 선언했을 경우에 반복문 속에서 sum의 의미는 각 사람이 기다리게 되는 하나의 시간이다.
   • 즉 sum끼리 더해준 값을 반환해주어야 한다.

 

코드

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] arg) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] inputs = br.readLine().split(" ");

        int[] times = new int[inputs.length];
        for (int i=0 ; i<n ; i++) 
            times[i] = Integer.parseInt(inputs[i]);

        Arrays.sort(times);

        int sum = 0;
        int answer = 0;
        for (int t : times) {
            sum += t;
            answer += sum;
        }

        System.out.println(answer);   
        return;
    }
}

 

1. String[] 타입 변수인 inputs에 각 사람들이 인출하는 데 걸리는 시간을 저장한다.
2. 한 번의 반복문을 통해 int[] 타입 변수인 times에 저장한다.
   • 정수형으로 변환 후 정렬해야 하기 때문이다.
3. Arrays.sort(times)를 통해 times를 오름차순으로 정렬한다.
4. 다시 반복문을 통해 sum(=해당 번째의 사람이 기다린 시간)을 구한다.
   • sum = 해당 번째의 직전까지 사람들의 인출 시간의 합 = 해당 번째의 사람이 기다린 시간
5. 변수 sum을 통해 answer(=기다린 시간 + 인출 시간)을 구한다.
   • answer = 기다린 시간 + 해당 번째의 사람이 인출하는 데 걸린 시간

 

제출 결과

 

 

제출을 하고 보니 이전에 맞았을 때보다 코드가 더 짧아지고 효율도 좋게 나왔다.