Lv.1mathqueuesimulation
매표소 줄
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
매표소 앞에 n명이 한 줄로 서 있습니다. 맨 앞 사람이 0번이고, i번 사람은 표를 tickets[i]장 사려고 합니다.
매표소는 1초에 한 장씩, 줄의 맨 앞 사람에게만 표를 팝니다. 표를 한 장 산 사람은
- 아직 더 사야 하면 줄의 맨 뒤로 가서 다시 서고,
- 원하는 만큼 다 샀으면 줄을 떠납니다.
줄을 옮겨 서는 데는 시간이 걸리지 않습니다. k번 사람이 원하는 표를 모두 사는 순간까지 몇 초가 걸리는지 반환하세요.
입출력 예
| tickets | k | result |
|---|---|---|
[2, 3, 2] | 2 | 6 |
[5, 1, 1, 1] | 0 | 8 |
[1] | 0 | 1 |
입출력 예 설명
예 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
제한 사항
-
tickets.length -
tickets[i] -
ktickets.length - 답은 32비트 정수 범위를 넘을 수 있습니다.
기대 복잡도
- 시간
- O(N)
- 공간
- O(1)
입출력 예
| tickets | k | 기대 출력 |
|---|---|---|
[2,3,2] | 2 | 6 |
[5,1,1,1] | 0 | 8 |
[1] | 0 | 1 |
힌트
힌트
줄은 사람들이 한 장씩 돌아가며 사는 바퀴로 움직입니다. k번 사람은 tickets[k]번째 바퀴에서 표를 다 삽니다. 그때까지 각 사람이 산 표의 수를 따로 세어 보세요.
k번보다 앞(또는k자신)에 있던 사람은tickets[k]번째 바퀴까지 사므로min(tickets[i], tickets[k])장을 삽니다.k번보다 뒤에 있던 사람은 마지막 바퀴에서k번보다 늦으므로min(tickets[i], tickets[k] - 1)장을 삽니다.
1초에 한 장씩 팔리므로 이 장수를 모두 더한 값이 답입니다.
복잡도 목표
줄을 1초씩 직접 흉내 내면 답만큼(최대 정도) 반복해야 하므로 시간 초과가 납니다. 사람마다 한 번씩만 보는 으로 풀 수 있습니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1000 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 12 | 판정만 |
| performance | 60 | 3 | 판정만 |