중요도 순 인쇄
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
사무실 프린터는 문서를 받은 순서대로 인쇄하지 않고, 중요도가 높은 문서를 먼저 인쇄합니다. 대기열에는 문서들이 priorities 순서대로 들어 있으며, priorities[i]는 i번째 문서의 중요도(1~9, 클수록 중요)입니다.
프린터는 다음 과정을 반복합니다.
- 대기열의 맨 앞 문서를 꺼냅니다.
- 대기열에 남은 문서 중 꺼낸 문서보다 중요도가 높은 문서가 하나라도 있으면, 꺼낸 문서를 대기열의 맨 뒤에 다시 넣습니다.
- 그렇지 않으면 꺼낸 문서를 인쇄합니다.
처음에 location번째(0부터 셈)에 있던 문서가 몇 번째로 인쇄되는지 반환하세요.
입출력 예
| priorities | location | result |
|---|---|---|
[2, 1, 3, 2] | 2 | 1 |
[1, 1, 9, 1, 1, 1] | 0 | 5 |
[1, 2, 3, 2, 1] | 4 | 4 |
입출력 예 설명
예 1 — 중요도 2, 1인 앞의 두 문서가 뒤로 밀려나고, 중요도 3인 2번 문서가 가장 먼저 인쇄됩니다.
예 2 — 중요도 9인 문서가 먼저 인쇄된 뒤, 대기열은 3, 4, 5, 0, 1번 문서 순서가 되어 0번 문서는 다섯 번째로 인쇄됩니다.
예 3 — 인쇄 순서는 2번(3), 3번(2), 1번(2), 4번(1), 0번(1) 문서입니다. 3번 문서가 인쇄된 뒤 대기열이 4, 0, 1번 순서이므로 1번 문서를 인쇄하기 전에 4번과 0번 문서가 뒤로 밀려나기 때문입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(priorities: int[], location: int) → int
제한 사항
-
priorities.length -
priorities[i] -
locationpriorities.length
기대 복잡도
- 시간
- O(N)
- 공간
- O(N)
입출력 예
| priorities | location | 기대 출력 |
|---|---|---|
[2,1,3,2] | 2 | 1 |
[1,1,9,1,1,1] | 0 | 5 |
[1,2,3,2,1] | 4 | 4 |
힌트
힌트
문서를 뒤로 보내도 남은 문서들의 원래 순서는 원형으로 그대로 유지됩니다. 대기열은 언제나 "남은 문서들을 원래 순서대로 늘어놓고, 어느 지점부터 시작하게 돌린 것"입니다.
그러므로 중요도 9인 문서부터 차례로, 현재 시작 위치에서 원형으로 한 바퀴 돌며 만나는 순서대로 인쇄된다고 보면 됩니다. 한 중요도를 다 인쇄하면, 마지막으로 인쇄한 문서의 바로 다음 위치가 새 시작 위치가 됩니다. 중요도가 9가지뿐이니 이렇게 해도 입니다.
복잡도 목표
대기열을 그대로 흉내 내면서 매번 "더 중요한 문서가 있는지" 대기열 전체를 훑으면 이 되어 효율성 테스트에서 시간 초과가 납니다. 중요도별 개수만 세어 두어도 "더 중요한 문서가 남았는가?"를 에 알 수 있습니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| 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 | 11 | 판정만 |
| performance | 60 | 3 | 판정만 |