[TIL 2024.07.16] 큐 자료구조

오늘 진행한 일들

• 알고리즘 강의 시청
• 알고리즘 코드 문제 풀이

알고리즘 문제

프린터 큐

• 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
• 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그 렇지 않다면 바로 인쇄를 한다.

작성한 코드

from collections import deque

t = int(input())

for i in range(t):
    n, m = list(map(int, input().split()))  
    queue = deque(map(int, input().split()))  
    idx = deque(range(0, n)) 

    order = 0

    while True:
        if queue[0] == max(queue): 
            order += 1
            if idx[0] == m:
                print(order)
                break
            else:
                queue.popleft()
                idx.popleft()
        else:
            queue.append(queue.popleft())
            idx.append(idx.popleft())

필요한 모듈 임포트

from collections import deque

deque 모듈을 사용하여 큐를 효율적으로 구현한다.

중요도 정렬 및 출력 순서

for i in range(t):
    n, m = list(map(int, input().split()))  
    queue = deque(map(int, input().split()))  
    idx = deque(range(0, n)) 

    order = 0

t만큼 반복하여 각 테스트 케이스를 처리한다. 문서의 수 n과 타겟 문서의 인덱스 m을 입력 받아 각각 변수에 저장하고, queue에는 문서의 중요도를, idx는 문서의 인덱스를 저장하는 큐를 사용한다.

while 루프

    while True:
        if queue[0] == max(queue): 
            order += 1
            if idx[0] == m:
                print(order)
                break
            else:
                queue.popleft()
                idx.popleft()
        else:
            queue.append(queue.popleft())
            idx.append(idx.popleft())

• if queue[0] == max(queue): 현재 문서의 중요도가 가장 크면, 출력 순서를 증가시키고 타겟 문서인지 확인한다.
• 타겟 문서인 경우, 출력하고 루프를 종료한다.
• 타겟 문서가 아니면 큐에서 문서를 제거하고 다음 문서를 확인한다.
• 현재 문서의 중요도가 가장 크지 않으면, 문서를 큐의 끝으로 이동시킨다.