[백준] 1966번 프린터 큐 파이썬 정답 코드

1966번: 프린터 큐

2번째 때 popleft( )를 popleft(0)으로 제출하여 런타임 에러가 발생했다...

---

1. 문제 내용

 

 

2. 접근 방식

• 문제에 언급된 조건을 그대로 구현하자.

현재 문서는 0번째이고, 이것보다 중요도가 높은 문서가 있는지 확인하기 위해 max( ) 내장함수를 사용하여 값을 비교한다. 만약 0번째보다 더 큰 중요도를 가진 문서가 있다면, 0번째 문서를 pop( )하고 큐의 맨 뒤에 추가한다.

 

• 실행 순서를 카운팅하기 위해 타겟 문서의 인덱스 m을 추적하자.

현재 문서보다 중요도가 높은 문서가 있어서 큐의 맨 뒤로 이동하든, 현재 문서가 프린트되든 타겟 문서의 인덱스 m은 1이 감소한다. 이때 만약 m == 0이지만, 이것보다 중요도가 더 높은 문서가 있다면 맨 뒤로 이동해야 하므로 m == len(큐) - 1이 된다. 반면 m == 0이고, 이것의 중요도가 가장 높다면 해당 문서가 출력된다.

 

 

3. 정답 코드

t = int(input())

for _ in range(t):
    n, m = map(int, input().split())
    data = list(map(int, input().split()))
    
    result = 1
    while data:
        if data[0] < max(data):
            data.append(data.pop(0))

        else:
            if m == 0: break

            data.pop(0)
            result += 1

        m = m - 1 if m > 0 else len(data) - 1

    print(result)

O(1)이 소요되는 popleft()를 사용하기 위해 deque 모듈을 사용한 코드도 제출해 보았지만, 데이터 양이 많지 않아서 그런지 오히려 실행 속도가 더 느려졌다. 중간 원소에 접근하는 데 상대적으로 느리기 때문일까?