문제
여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.
현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.
예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.
여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.
입력
3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1
출력
1
2
5
문제 이해
역시나 문제 이해가 어려웠다. 문제 이해하는 시간이 더 드는 기분이랄까.
3 👉 총 테스터 케이스의 수
📃1번째 테스터 케이스
1 0 👉 총 문서의 수, 인쇄 할 문서의 인덱스 값
5 👉 문서의 중요도
📃2번째 테스터 케이스
4 2
1 2 3 4
📃3번째 테스터 케이스
6 0
1 1 9 1 1 1
이렇게 이해하심 됩니다... (ˉ﹃ˉ)
4 2
1 2 3 4
그럼 이 부분은 총 문서의 수는 4개, 그 중 2번 인덱스 문서 즉, 3번째 문서의 인쇄 순서를 알아내야 하는 것이죠. 그리고 인덱스 0~3의 문서는 각각 1 2 3 4의 중요도를 가집니다.
의사 코드
- 총 테스터 케이스의 수 T 입력 받기
- T만큼 테스트 조건 입력 받기
n:문서의 수, m: 인쇄할 문서 인덱스 입력 받기
중요도 데크 입력 받기
n만큼 인덱스 데크 생성 - 인쇄 순서 저장할 변수 cnt 생성
- imp_que에서 m의 인쇄 순서(cnt) 찾기
👉조건문 1. imp_que의 첫 요소가 최대라면 인쇄
👉조건문 1-1. 인쇄한 요소의 인덱스와 m이 같다면 성공
👉조건문 1. imp_que의 첫 요소가 최대 아니라면 리스트 뒤로 보내기
✨collections.deque
문제에서는 큐를 언급했지만 데크를 사용하면 더 유연하게 연산할 수 있습니다. 데크는 전단, 후단에서 양방향으로 삽입, 삭제 연산을 할 수 있기 때문입니다.
from collections import deque
👉 d = deque([1, 2, 3])
에서 전단에서 삽입, 삭제 후단에서 삽입, 삭제가 가능합니다.
d.append(4)
>>[1, 2, 3, 4]
d.appendleft(0)
>>[0, 1, 2, 3, 4]
d.pop()
>>[0, 1, 2, 3]
d.popleft()
>>[1, 2, 3]
이 문제에선 popleft() 함수로 선입된 요소를 선출하는 게 가능합니다.
제출
from collections import deque #데크 함수 사용
#테스트 수 입력 받기
T = int(input())
#각 테스트 조건 입력 받기
for _ in range(T):
n, m = map(int,input().split()) # n:문서 수 m:인쇄 문서의 인덱스
imp_que = deque(map(int,input().split())) # 중요도 입력 받기
idx_que = deque(list(range(n))) # 각 문서에 인덱스 부여
cnt = 0 #인쇄 순서 변수 초기화
while imp_que:
if imp_que[0] == max(imp_que): #만약 중요도의 첫 요소가 최대라면(인쇄함)
cnt += 1 #순서 +1
imp_que.popleft() #첫 요소 삭제
if idx_que.popleft() == m: #만약 인덱스 첫 요소와 m이 같다면
print(cnt) #순서 출력
else: #중요도의 첫 요소가 최대가 아니라면(인쇄 안 하고 리스트 마지막으로 넘김)
imp_que.append(imp_que.popleft())
idx_que.append(idx_que.popleft())