Funcia
Lv.1countingqueuesimulation

중요도 순 인쇄

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

사무실 프린터는 문서를 받은 순서대로 인쇄하지 않고, 중요도가 높은 문서를 먼저 인쇄합니다. 대기열에는 문서들이 priorities 순서대로 들어 있으며, priorities[i]는 i번째 문서의 중요도(1~9, 클수록 중요)입니다.

프린터는 다음 과정을 반복합니다.

  1. 대기열의 맨 앞 문서를 꺼냅니다.
  2. 대기열에 남은 문서 중 꺼낸 문서보다 중요도가 높은 문서가 하나라도 있으면, 꺼낸 문서를 대기열의 맨 뒤에 다시 넣습니다.
  3. 그렇지 않으면 꺼낸 문서를 인쇄합니다.

처음에 location번째(0부터 셈)에 있던 문서가 몇 번째로 인쇄되는지 반환하세요.

입출력 예

prioritieslocationresult
[2, 1, 3, 2]21
[1, 1, 9, 1, 1, 1]05
[1, 2, 3, 2, 1]44

입출력 예 설명

예 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

제한 사항

  • 1≤1 \le priorities.length ≤200,000\le 200{,}000
  • 1≤1 \le priorities[i] ≤9\le 9
  • 0≤0 \le location << priorities.length

기대 복잡도

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

입출력 예

prioritieslocation기대 출력
[2,1,3,2]21
[1,1,9,1,1,1]05
[1,2,3,2,1]44

힌트

힌트

문서를 뒤로 보내도 남은 문서들의 원래 순서는 원형으로 그대로 유지됩니다. 대기열은 언제나 "남은 문서들을 원래 순서대로 늘어놓고, 어느 지점부터 시작하게 돌린 것"입니다.

그러므로 중요도 9인 문서부터 차례로, 현재 시작 위치에서 원형으로 한 바퀴 돌며 만나는 순서대로 인쇄된다고 보면 됩니다. 한 중요도를 다 인쇄하면, 마지막으로 인쇄한 문서의 바로 다음 위치가 새 시작 위치가 됩니다. 중요도가 9가지뿐이니 이렇게 해도 O(9N)O(9N)입니다.

복잡도 목표

대기열을 그대로 흉내 내면서 매번 "더 중요한 문서가 있는지" 대기열 전체를 훑으면 O(N2)O(N^2)이 되어 효율성 테스트에서 시간 초과가 납니다. 중요도별 개수만 세어 두어도 "더 중요한 문서가 남았는가?"를 O(1)O(1)에 알 수 있습니다.

언어별 시간 제한

언어효율성 시간 제한
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입력·출력 공개
correctness4011판정만
performance603판정만
에디터 불러오는 중…

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