[백준] 1966번: 프린터 큐 - Python

링크: https://www.acmicpc.net/problem/1966

 

아이디어

• 전체 테스트 케이스와 테스트 케이스 별 처리 과정 2중 반복문으로 O(N^2) 시간 복잡도를 가진다.
• deque 라이브러리를 활용해 큐 자료구조 다루자
• 반복마다 pop 이벤트가 나오면 cnt 값을 증가시키자
• 반복마다 M값을 변경하여 원하는 값의 위치를 최신화 하자
• 반복마다 맨 앞의 값이 큐의 최대값인지 아닌지로 분기를 나눈다.
• 맨 앞의 값이 최대값인 경우 (우선순위가 가장 높은 경우)
  • M이 0 이면 cnt 값을 출력하고 반복문을 끝내 다음 테스트 케이스로 넘어간다
  • 아니면 M의 값을 1 감소, 맨 앞의 값 popleft()로 뺌, cnt 1증가
• 맨 앞의 값이 최대값이 아닌 경우 (우선순위가 가장  높지 않은 경우)
  • M이 0이면 맨 뒤에 붙여줘야 하니 값을 len(q)-1로 변경
  • 아니면  단순히 M을 1 감소
  • rotate(-1)을 통해 맨 앞의 값을 맨 뒤로 보내기

코드

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

T = int(input())

for i in range(T):
    N, M = map(int, input().split())
    q = deque(input().strip().split())
    cnt = 1
    while 1:
        if q[0] == max(q):
            if M == 0:
                print(cnt)
                break
            else:
                M -=1
                q.popleft()
                cnt +=1
        else:
            if M == 0:
                M = len(q)-1
            else:
                M-=1
            q.rotate(-1)

마무리

deque 사용법을 간단히 리마인드 시켜볼 수 있었던 문제였다.

단순 상황별 처리 과정을 바로 떠올리는 감이 많이 떨어진거 같다 열심히 해야지