백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-1966 프린터 큐 편 (python)

문제 살펴보기!!

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

반응형

솔루션 살펴보기!!

from collections import deque

def process_print_queue(N, M, priorities):
    queue = deque((priority, idx) for idx, priority in enumerate(priorities))  # 우선순위와 인덱스를 함께 저장
    printed_count = 0  # 출력된 문서의 수

    while queue:
        # 가장 앞에 있는 문서의 우선순위가 가장 큰지 확인
        if queue[0][0] == max(queue, key=lambda x: x[0])[0]:
            printed_count += 1  # 문서 출력
            priority, index = queue.popleft()

            if index == M:  # 목표 문서가 출력된 경우
                return printed_count
        else:
            queue.rotate(-1)  # 우선순위가 가장 크지 않으면 회전

def main():
    T = int(input())  # 테스트 케이스의 수
    for _ in range(T):
        N, M = map(int, input().split())  # 문서의 수 N, 목표 문서의 인덱스 M
        priorities = list(map(int, input().split()))  # 문서들의 우선순위
        result = process_print_queue(N, M, priorities)
        print(result)

if __name__ == "__main__":
    main()

코드 흐름 설명

이 코드는 프린터 큐 문제를 해결하기 위한 코드로, 문서들이 우선순위에 따라 출력되며, 목표 문서가 몇 번째로 출력되는지를 계산합니다. 각각의 테스트 케이스에 대해, 문서의 우선순위를 큐로 처리하며 조건에 맞춰 회전시킵니다.

코드 흐름:

1. 입력 처리 (main 함수):
   • T는 테스트 케이스의 수를 입력받습니다.
   • 각 테스트 케이스마다:
     • N(문서의 수)와 M(목표 문서의 인덱스)을 입력받습니다.
     • 문서의 우선순위 배열을 입력받고, 이를 이용해 process_print_queue 함수를 호출하여 결과를 출력합니다.
2. 큐 처리 (process_print_queue 함수):
   • 문서의 우선순위와 해당 문서의 인덱스를 큐에 넣습니다. queue = deque((priority, idx) for idx, priority in enumerate(priorities))는 각 문서를 (우선순위, 인덱스) 형식으로 저장하는 큐를 생성합니다.
   • printed_count는 몇 번째 문서가 출력되었는지를 추적하는 변수입니다.
   • 큐가 빌 때까지 반복합니다:
     • 큐의 첫 번째 문서가 현재 큐에서 우선순위가 가장 높은 문서인지 확인합니다. 이때 max(queue, key=lambda x: x[0])[0]로 큐 내에서 가장 높은 우선순위를 가진 문서를 찾습니다.
     • 만약 첫 번째 문서가 가장 높은 우선순위라면, 해당 문서를 출력(popleft())하고 printed_count를 증가시킵니다.
     • 그 문서가 목표 문서(M)인 경우, printed_count를 반환하고 종료합니다.
     • 만약 첫 번째 문서가 우선순위가 가장 높지 않다면, 큐를 회전(rotate(-1))시켜 문서의 순서를 한 칸 뒤로 밀어냅니다.
3. 출력:
   • 각 테스트 케이스마다 목표 문서가 몇 번째로 출력되었는지를 출력합니다.

728x90

주요 개념 설명

1. 큐 (deque):
   • 큐는 선입선출(FIFO, First-In-First-Out) 방식으로 작동하는 자료구조입니다. 하지만 deque는 양방향 큐로, 양쪽 끝에서 모두 삽입과 삭제가 가능합니다.
   • popleft()를 통해 큐의 맨 앞에 있는 요소를 제거하고, rotate()를 통해 큐를 회전시켜 문서의 순서를 변경합니다.
   • 이 코드에서는 문서의 우선순위와 인덱스를 함께 관리하기 위해 (priority, idx) 형식으로 저장한 큐를 사용합니다.
2. rotate():
   • rotate(n)은 큐의 요소들을 n만큼 회전시키는 함수입니다.
   • n이 양수이면 오른쪽으로, 음수이면 왼쪽으로 회전합니다. 이 코드는 rotate(-1)을 사용해 큐의 첫 번째 요소를 뒤로 밀어냅니다.
3. 최대값(max) 함수:
   • max(queue, key=lambda x: x[0])는 큐 내에서 우선순위를 기준으로 가장 큰 값을 찾아냅니다. 이때 큐 안에 저장된 각 요소는 (우선순위, 인덱스) 형태로 저장되기 때문에, 우선순위인 첫 번째 값을 기준으로 최대값을 찾습니다.
   • 현재 큐에서 가장 높은 우선순위의 문서가 무엇인지를 매번 확인하기 위해 max()를 사용합니다.
4. 문서의 우선순위:
   • 각 문서가 특정 우선순위를 가지고 있고, 우선순위가 높은 문서부터 출력됩니다. 이 코드는 매번 현재 큐에서 우선순위가 가장 높은 문서를 확인하고, 그렇지 않으면 큐를 회전시키는 방식으로 문제를 해결합니다.
5. 목표 문서의 인덱스:
   • 각 문서는 고유한 인덱스를 가지며, 목표 문서(M)가 몇 번째로 출력되는지를 확인하는 것이 이 문제의 핵심입니다.
   • 목표 문서의 인덱스가 출력될 때까지 회전과 출력 과정을 반복합니다.