1966 프린터 큐

1966번: 프린터 큐 (acmicpc.net)

1966번: 프린터 큐

tnum = int(input())
temp = []
for _ in range(tnum):
    N,M = map(int, input().split())
    pr = list(map(int, input().split()))
    temp = [0 for _ in range(N)] 
    temp[M] = 1
    count = 0

    while True:
        if pr[0] == max(pr):
            count += 1
            if temp[0] != 1:
                pr.pop(0)
                temp.pop(0)
            else:
                print(count)
                break
        else:
            pr.append(pr[0])
            temp.append(temp[0])
            del pr[0]
            del temp[0]

이 문제는 주어진 인덱스가 어느 위치에 있는지, 몇번째로 프린터에서 출력되게 해야하는지를 구하는 문제이다.

우선,같은 크기의 두가지 배열의 인덱스가 필요하다는 아이디어까지는 있었는데 실현시키진 못했었다.

1.실제 값을 담는 배열

2.인덱싱된 값을 담는 배열

두 가지를 같이 움직여야 한다.

이 문제의 답을 가장 탐욕적으로 구하기 위해서는 (아마) 정렬되면 첫번째에 있는 수는 빠져나가게 하고, 그렇게 계속 빠져나가게 하면서 우리가 구하고자 하는 그 값이 출력될 때 지금까지 저장했던 count값을 출력하면 되는 문제였다.

우선 queue의 구조를 알아야 한다.

del pr[0] = pr.pop[0]와 같은 역할로, 해당하는 인덱스의 값을 배열에서 지우는 역할을 할 수 있다.

max(pr) 배열에서 가장 큰 값을 나타내는 역할을 한다.