Funcia
Lv.1mathqueuesimulation

매표소 줄

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

매표소 앞에 n명이 한 줄로 서 있습니다. 맨 앞 사람이 0번이고, i번 사람은 표를 tickets[i]장 사려고 합니다.

매표소는 1초에 한 장씩, 줄의 맨 앞 사람에게만 표를 팝니다. 표를 한 장 산 사람은

  • 아직 더 사야 하면 줄의 맨 뒤로 가서 다시 서고,
  • 원하는 만큼 다 샀으면 줄을 떠납니다.

줄을 옮겨 서는 데는 시간이 걸리지 않습니다. k번 사람이 원하는 표를 모두 사는 순간까지 몇 초가 걸리는지 반환하세요.

입출력 예

ticketskresult
[2, 3, 2]26
[5, 1, 1, 1]08
[1]01

입출력 예 설명

예 1 — 첫 바퀴에 세 명이 한 장씩 사서 3초, 남은 표는 [1, 2, 1]입니다. 둘째 바퀴에 0번, 1번, 2번 순서로 한 장씩 사면 6초째에 2번 사람이 다 삽니다.

예 2 — 1초째 0번이 한 장 사고 뒤로 가며, 2~4초에 나머지 세 명이 한 장씩 사고 떠납니다. 그 뒤 0번이 혼자 남은 4장을 사므로 8초입니다.

예 3 — 1초 만에 끝납니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(tickets: int[], k: int) → long

제한 사항

  • 1≤1 \le tickets.length ≤200,000\le 200{,}000
  • 1≤1 \le tickets[i] ≤109\le 10^9
  • 0≤0 \le k << tickets.length
  • 답은 32비트 정수 범위를 넘을 수 있습니다.

기대 복잡도

시간
O(N)
공간
O(1)

입출력 예

ticketsk기대 출력
[2,3,2]26
[5,1,1,1]08
[1]01

힌트

힌트

줄은 사람들이 한 장씩 돌아가며 사는 바퀴로 움직입니다. k번 사람은 tickets[k]번째 바퀴에서 표를 다 삽니다. 그때까지 각 사람이 산 표의 수를 따로 세어 보세요.

  • k번보다 앞(또는 k 자신)에 있던 사람은 tickets[k]번째 바퀴까지 사므로 min(tickets[i], tickets[k])장을 삽니다.
  • k번보다 뒤에 있던 사람은 마지막 바퀴에서 k번보다 늦으므로 min(tickets[i], tickets[k] - 1)장을 삽니다.

1초에 한 장씩 팔리므로 이 장수를 모두 더한 값이 답입니다.

복잡도 목표

줄을 1초씩 직접 흉내 내면 답만큼(최대 101410^{14} 정도) 반복해야 하므로 시간 초과가 납니다. 사람마다 한 번씩만 보는 O(N)O(N)으로 풀 수 있습니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251000 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4012판정만
performance603판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.