1966 프린터큐

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
read = sys.stdin.readline
from collections import deque

T = int(input())
N_array = []
M_array = []
K_array = []

for t in range(T):

    N, M = map(int, read().split())
    # N은 문서의 개수, M은 내가 궁금한 문서가 현재 몇번째에 놓여있는지
    K = list(map(int, read().split()))

    N_array.append(N)
    M_array.append(M)
    K_array.append(K)

cnt_array = []

for i in range(T):

    N = N_array[i]
    M = M_array[i]
    K = K_array[i]

    q = deque(K)
    ordered = [-1]*N
    ordered[M] = 1
    q_ordered = deque(ordered)
    cnt = 0

    # 무한 루프를 돌아야함.
    while True :
        now = q.popleft()
        now_orderd = q_ordered.popleft()
        # q에서 자신을 제외되었고,
        # 남은 queue에서 자기보다 큰게 없으면 출력하면 되니까 max()를 사용하자
        if len(q) < 1 :
            cnt += 1
            cnt_array.append(cnt)
            break
        if max(q) <= now :
            cnt += 1
            if now_orderd == 1 :
                cnt_array.append(cnt)
                break
        # 만약 자신보다 큰게 존재한다면, 다시 queue의 오른쪽에 넣자.
        else :
            q.append(now)
            q_ordered.append(now_orderd)

for z in range(len(cnt_array)):

    print(cnt_array[z])

3. 문제 풀이

생각보다 시뮬레이션 문제가 생각을 해내야하고 어떻게 할지 고민을 많이해야해서 시간을 많이 잡아먹는다.. 꾸준하게 많은 유형을 접해서 어떻게 빠르게 효율적인 결과를 낼지 고민해야겠다.

이 문제는 queue를 이용하는 문제이다. 이때, 나는 원래 array뿐 아니라 순서까지 적혀있는 array를 만들어서 2개의 큐를 같이 움직였다.

queue로 데이터를 뽑으면 남은 queue의 maximum 값이 뽑힌 값보다 큰게 없으면, 이것은 출력해도 된다. 반대라면 출력하지않고 다시 append한다. 이것을 반복하면서 count를 쌓다가 타겟 데이터의 순서가 오면 count를 count array에 append하면서 무한 루프를 break한다.