모든 챌린지
보통 0명 해결 정답률 0%

은행 대기열 시뮬레이션

손님들이 한 줄로 서서 여러 은행 창구를 기다리는 상황을 시뮬레이션하고 대기 시간을 알려 줍니다.

배우게 될 내용

  • 먼저 온 손님부터 먼저 처리한다
  • 각 창구가 언제 비는지 추적한다
  • 시뮬레이션에서 요약 통계를 모은다

문제

원문 보기 (영어)

어느 은행에는 창구 직원 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

예시

예시 1
입력:
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]입니다.

예시 2
입력:
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에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.