문제
여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 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번째로 인쇄되게 된다.
입력
첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.
테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.
출력
각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.
예제 입력 1
3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1예제 출력 1
1
2
5문제 풀이
def printer_queue(queue,m):
cnt=1
while queue:
num=queue.pop(0)
for i in range(len(queue)):
if num[0]<queue[i][0]:
queue.append(num)
break
else:
if i==len(queue)-1:
if num[1]==m:
return cnt
else:
cnt+=1
return cnt
T=int(input())
for _ in range(T):
n,m=map(int,input().split())
input_queue=list(map(int,input().split()))
queue=[(input_queue[i],i) for i in range(len(input_queue))]
print(printer_queue(queue,m))리스트에 숫자를 넣고 0번째 숫자가 제일 큰 숫자라면 그대로 출력하고 그게 아니라면 뽑아서 리스트의 맨 뒤로 보내면서 원하는 자리에 있었던 숫자가 print되는 순서를 출력하는 문제였다.
손으로 풀면 금방 풀릴 문제였는데 queue에 넣고 비교하고 원래 있었던 위치도 체크하면서 하려니 고려해야할 사항이 많았다.
우선 초기에 받은 숫자 리스트에 원래의 위치인 인덱스를 함께 묶어 추가해준다.
이렇게 하면 숫자의 인덱스가 바뀌어도 원래 위치를 할 수 있다.
queue가 빌때까지 반복하여 제일 앞에 있는 숫자가 크면 출력을 하도록 했는데 if문을 이용하여 리스트의 마지막 숫자까지 비교했을 때에도 0번째 위치의 숫자가 제일 크다면 그대로 출력하게 했다.
이때, 우리가 원하는 위치에 있던 값이라면 return cnt으로 순서값을 반환해주고 그게 아니라면 다른 숫자가 출력되었다는 뜻이기 때문에 cnt, 즉 순서값을 하나 더 올려줬다.
이렇게 하면 정답으로 체크된다!
놓쳤던 부분
- 입력으로 주어지는 숫자의 위치도 인덱스처럼 0번째 위치가 제일 왼쪽이었는데 잘 못 파악해서 처음에 1번이 제일 왼쪽 숫자라고 체크해서 답이 계속 안나왔다.
queue=[(input_queue[i],i) for i in range(len(input_queue))]여기서 (input_queue[i],i+1) 이라고 해주고 답이 안 나와서 시간이 걸렸다.
여담
백준으로 제출했을 때 한 번만에 정답이 되었다!
