문제
어느 은행에는 창구 직원 tellers명과 대기 줄 하나가 있습니다. i번 손님은 arrivals[i]분에 도착하며 창구에서 service[i]분이 걸립니다. 손님은 반드시 도착 순서(리스트의 순서)대로 처리됩니다. 줄 맨 앞에 선 손님은 가장 먼저 비는 창구로 가며(동시에 비면 번호가 가장 작은 창구), 자신의 도착 시각과 그 창구가 비는 시각 중 더 늦은 시각에 업무를 시작합니다. 모든 창구는 0분부터 비어 있습니다.
손님의 대기 시간은 시작 시각에서 도착 시각을 뺀 값입니다.
bank_queue_simulation(arrivals, service, tellers) 함수를 구현하세요.
입력
arrivals: 도착 시각(분)으로, 감소하지 않는 순서입니다.
service: 손님별 업무 시간(분)으로, 순서는 같습니다.
tellers: 창구 직원 수입니다.
출력
[total_wait, longest_wait, last_finish], 즉 대기 시간의 합, 가장 긴 대기 시간, 마지막 손님의 업무가 끝나는 시각을 반환하세요. 손님이 없으면 [0, 0, 0]을 반환합니다.
제약 조건
0 ≤ 손님 수 ≤ 2,000
0 ≤ arrival ≤ 100,000
1 ≤ service ≤ 1,000
1 ≤ tellers ≤ 20
예시
입력:
arrivals = [0, 1, 2, 3]
service = [5, 3, 4, 2]
tellers = 2
예상 출력:
expected = [4, 2, 8]
입력:
std::vector<long long> arrivals = {0, 1, 2, 3};
std::vector<long long> service = {5, 3, 4, 2};
long long tellers = 2;
예상 출력:
std::vector<long long> expected = {4, 2, 8};
입력:
long[] arrivals = new long[] {0, 1, 2, 3};
long[] service = new long[] {5, 3, 4, 2};
long tellers = 2;
예상 출력:
long[] expected = new long[] {4, 2, 8};
설명
1번과 2번 손님은 바로 시작합니다(0분과 1분). 2번 창구가 4분에 비므로 3번 손님은 2분을 기다리고, 1번 창구가 5분에 비므로 4번 손님도 2분을 기다립니다. 마지막 종료 시각은 max(8, 7) = 8이므로 [4, 2, 8]입니다.
입력:
arrivals = [0, 0, 0]
service = [4, 4, 4]
tellers = 1
예상 출력:
expected = [12, 8, 12]
입력:
std::vector<long long> arrivals = {0, 0, 0};
std::vector<long long> service = {4, 4, 4};
long long tellers = 1;
예상 출력:
std::vector<long long> expected = {12, 8, 12};
입력:
long[] arrivals = new long[] {0, 0, 0};
long[] service = new long[] {4, 4, 4};
long tellers = 1;
예상 출력:
long[] expected = new long[] {12, 8, 12};
설명
창구가 하나뿐이면 대기 시간은 0, 4, 8분이고 마지막 손님은 12분에 끝나므로 [12, 8, 12]입니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
각 창구가 비는 시각(분)을 담은 배열을 두세요.
힌트 2
손님마다 가장 빨리 비는 창구를 고르세요(동시에 비면 인덱스가 가장 작은 창구).
힌트 3
시작 시각은 도착 시각과 창구가 비는 시각 중 늦은 쪽이고, 대기 시간은 시작 시각에서 도착 시각을 뺀 값입니다.
예상 복잡도
시간 O(n × k), 추가 공간 O(k)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.