[Python] 백준 1966 프린터 큐

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

1966번: 프린터 큐

 

 

문제 해결 포인트

- 자료구조 큐

- 순서를 나타내는 두개의 변수를 잘 구분하여 인지하여야한다.

       * 남은 우선순위 중 최대값이므로 출력하는 순서

       * 초기 큐의 각 문서 순서

 

- 큐에 (중요도, 위치) 값을 삽입한다. 위치값을 삽입하는 이유는 M과 비교하여 찾는 문서인지 확인하기 위함

- 초기 큐를 내림차순으로 정렬한다.

   매번 큐의 최대값을 구하는 것보다 인덱스 변수(no)를 두어 확인하는 것이 효율적이기 때문

- 큐를 돌며 최대값과 같다면 최대값 인덱스 += 1

- 만약 찾는 위치(M)과 출력할 최대값이 같다면 출력 순서(no) 출력 후 종료

 

작성 코드

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

T = int(input())  # 테스트케이스
for _ in range(T):
    N, M = map(int, input().split())   # N, M 입력 받기
    numbers = list(map(int, input().split()))  # 초기 큐 입력 받기
    que = deque()
    for i in range(N):
        que.append((numbers[i], i))  # 우선순위, 초기 위치 큐에 삽입

    no = 1  # 출력 순서
    numbers.sort(reverse=True)  # 우선순위가 큰 값부터 출력하므로 내림차순 정렬

    while que:
        q = que.popleft()
        if q[0] == numbers[no-1]:  # 꺼낸 값이 남은 값중 최대값일 때
            if q[1] == M:  # 찾는 위치의 값일 때
                print(no)
                break
            no += 1  # 최대값 업데이트
        else:
            que.append(q)  # 최대값이 아닐 때 큐의 맨 뒤로 삽입

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚