문제 설명
당신은 ATM 기계에 서 있습니다. ATM에서 돈을 인출하기 위해서는 몇 가지 과정을 거쳐야 합니다.
각 사용자마다 인출을 완료하기까지 걸리는 시간이 다르며, 이 시간은 사용자가 ATM에서 기능을 수행하는 데 걸리는 시간입니다.
사용자는 `n`명의 사용자가 있으며, 각 사용자의 인출 시간이 주어질 때, 모든 사용자가 인출을 완료하는 데 걸리는 총 시간을 계산하는 함수를 작성해야 합니다.
문제 입력
- 첫 번째 줄: 사용자 수를 나타내는 정수 `n` (1 ≤ n ≤ 1000)
- 두 번째 줄: 각 사용자의 인출 시간을 나타내는 `n`개의 정수 (1 ≤ 시간 ≤ 10000)
문제 출력
모든 사용자들이 인출을 완료하기까지 걸리는 총 시간을 출력한다.
예제 입력
5
3 1 4 3 2
예제 출력
32
문제 분석
모든 사용자가 ATM에서 인출을 마치는데 걸리는 총 시간은, 각 사용자가 인출을 완료할 때까지 대기해야하는 다른 사용자들의 시간을 포함해야 합니다.
즉, 특정 사용자가 인출을 마치는 데 걸리는 시간은 그 사람의 인출 시간과 그 이전까지 인출을 마친 모든 사람의 시간이 더해진 값이 됩니다.
이를 통해 모든 사용자의 인출 완료 시간을 계산할 수 있습니다.
문제 해결 방법
- 사용자의 인출 시간을 입력받아 배열에 저장합니다.
- 입력받은 인출 시간을 오름차순으로 정렬합니다.
- 총 인출 시간을 계산하기 위해, 각 사용자의 인출 완료 시간을 누적합 형태로 계산합니다.
- 모든 사용자의 인출 완료 시간을 합산하여 최종 시간을 구합니다.
자바 코드 구현
import java.util.Arrays;
import java.util.Scanner;
public class ATMWithdrawal {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 사용자 수 입력
int n = sc.nextInt();
int[] times = new int[n];
// 인출 시간 입력
for (int i = 0; i < n; i++) {
times[i] = sc.nextInt();
}
// 시간 배열 정렬
Arrays.sort(times);
// 누적 시간 변수
int totalTime = 0;
int accumulatedTime = 0;
// 각 사용자에 대해 누적 시간 계산
for (int time : times) {
accumulatedTime += time; // 현재 사용자의 인출 시간 추가
totalTime += accumulatedTime; // 총 시간에 누적 시간 추가
}
// 결과 출력
System.out.println(totalTime);
sc.close();
}
}
코드 설명
위의 자바 코드는 ATM 인출 시간 계산 문제를 해결하기 위해 다음과 같은 과정으로 구성되어 있습니다:
- 먼저 입력을 받기 위해 Scanner 객체를 생성하고 사용자의 수
n을 입력받습니다. - 그 다음, 각 사용자의 인출 시간을 입력받아 배열
times에 저장합니다. Arrays.sort(times)를 통해 인출 시간을 오름차순으로 정렬합니다. 이는 각 사용자의 대기 시간을 최소화하기 위해 중요합니다.- 총 인출 시간을 계산하기 위해 두 개의 변수를 사용합니다:
totalTime는 모든 사용자가 인출을 완료하는 데 걸린 총 시간을 저장하고,accumulatedTime는 현재까지의 누적 시간을 저장합니다. - 각 사용자의 인출 시간을 순회하면서, 해당 사용자의 인출 시간이 누적된 시간에 추가되고, 이를 총 시간에 더합니다.
- 마지막으로 총 인출 시간을 출력합니다.
시간 복잡도 분석
이 알고리즘의 시간 복잡도는 주로 인출 시간 배열을 정렬하는 데 의존합니다.
배열을 정렬하는 가장 일반적인 정렬 알고리즘인 퀵 정렬의 평균 시간 복잡도가 O(n log n)이므로, 전체 알고리즘의 시간 복잡도는 O(n log n)입니다.
이후 인출 시간을 누적하는 작업은 한 번의 반복으로 해결되므로 O(n)입니다.
따라서 전체 시간 복잡도는 O(n log n)입니다.
종합 정리
이 강좌에서는 ATM 인출 시간 계산 문제를 통해 기본적인 배열 정렬과 누적 합산을 연습할 수 있었습니다.
대부분의 알고리즘 문제는 기본적인 데이터 구조와 알고리즘을 통해 해결될 수 있습니다.
인출 시간이 적절히 최적화되면 대기 시간이 줄어들고, 결과적으로 모든 사용자들이 ATM을 사용하는 데 있어 더 효율적일 것입니다.
이와 같은 문제를 통해 다양한 알고리즘과 자료구조를 활용하여 취업 준비에 도움이 되는 연습을 할 수 있습니다.