오늘 문제는 우선순위라는 개념을 큐에 도입한 문제입니다. 일종의 우선순위 큐라고 봐도 되겠죠?
오늘 문제 한 번 살펴볼까요?
1. 오늘의 학습 키워드
- 큐
2. 문제: 프린터 큐 (1966번)
- 단계: 🥈실버 3티어
- 알고리즘 분류: 구현, 자료 구조, 시뮬레이션, 큐
- 출처: https://www.acmicpc.net/problem/1966
프린터 큐
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 83414 | 48260 | 38034 | 58.715% |
문제
여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.
- 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
- 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.
예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.
여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.
입력
첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.
테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.
출력
각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.
예제 입력 1 복사
3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1
예제 출력 1 복사
1
2
5
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2006 F번
알고리즘 분류
3. 나의 풀이
문제 이해 및 접근
이 문제는 프린터가 문서를 인쇄하는 순서를 시뮬레이션하는 문제입니다. 기본적인 큐(Queue) 구조를 기반으로 하되, 우선순위를 고려하여 문서를 인쇄하는 방식을 구현해야 합니다. 프린터가 FIFO(First In First Out) 방식으로 동작하는 것이 아니라, 큐에 있는 문서들 중 가장 중요도가 높은 문서부터 인쇄하는 방식입니다.
문제의 핵심은 문서의 중요도를 기반으로 인쇄 순서를 결정하는 것입니다. 큐에 있는 문서들의 중요도를 비교하면서, 더 높은 중요도의 문서가 있다면 현재 문서를 큐의 맨 뒤로 보내는 작업을 반복합니다. 이런 과정을 거쳐 목표 문서가 몇 번째로 인쇄되는지 알아내는 것이 이 문제의 목표입니다.
문제에서 주어진 조건을 잘 살펴보면:
- 문서의 중요도를 확인하여 중요도가 더 높은 문서가 있으면, 그 문서를 먼저 인쇄해야 합니다.
- FIFO 구조를 사용하지만, 중요도에 따라 순서를 재조정하므로, 우선순위 큐(Priority Queue)와 유사한 동작을 하게 됩니다.
이 문제는 기본적으로 큐를 사용한 시뮬레이션 문제로 볼 수 있으며, 중요도에 따라 동작하는 조건을 정확히 반영하는 것이 핵심입니다.
코드 분석
이제 위 문제를 해결하기 위한 코드를 분석해보겠습니다.
import sys
from collections import deque
T = int(sys.stdin.readline().strip())
for _ in range(T):
N, M = map(int, sys.stdin.readline().split())
priority = list(map(int, sys.stdin.readline().split()))
queue = deque((i, p) for i, p in enumerate(priority))
print_order = 0
while queue:
current = queue.popleft()
# 현재 문서보다 중요도가 높은 문서가 있는지 확인
if any(current[1] < q[1] for q in queue):
queue.append(current) # 중요도가 높은 문서가 있으면 뒤로 보냄
else:
print_order += 1 # 인쇄됨
if current[0] == M: # 우리가 찾는 문서라면
print(print_order) # 인쇄 순서를 출력
break
1. 입력 처리
T = int(sys.stdin.readline().strip())
- 먼저 테스트케이스의 개수
T를 입력받습니다. 여러 테스트케이스에 대해 반복적으로 처리해야 하므로, 각 테스트케이스마다 루프를 돌게 됩니다.
2. 큐 초기화
N, M = map(int, sys.stdin.readline().split())
priority = list(map(int, sys.stdin.readline().split()))
queue = deque((i, p) for i, p in enumerate(priority))
N: 문서의 개수,M: 우리가 관심 있는 문서의 현재 위치입니다.priority: 각 문서의 중요도가 담긴 리스트입니다.queue: 문서의 인덱스와 중요도를 튜플 형태로 큐에 저장합니다. 여기서enumerate를 사용하여 문서의 인덱스와 중요도를 함께 저장한 이유는, 나중에 인덱스를 사용해 우리가 찾는 문서인지 확인하기 위해서입니다.
3. 큐 처리
while queue:
current = queue.popleft()
if any(current[1] < q[1] for q in queue):
queue.append(current)
else:
print_order += 1
if current[0] == M:
print(print_order)
break
current = queue.popleft(): 큐의 맨 앞에 있는 문서를 꺼냅니다.if any(current[1] < q[1] for q in queue): 나머지 큐에 있는 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있는지 확인합니다. 만약 중요도가 높은 문서가 있으면, 그 문서를 큐의 맨 뒤로 보냅니다.- 중요도가 더 높은 문서가 없다면 현재 문서를 인쇄하고, 인쇄 순서를 1 증가시킵니다.
current[0]이 우리가 찾는 문서(M)라면, 인쇄 순서를 출력하고 루프를 종료합니다.
이 코드는 각 테스트케이스에 대해 주어진 조건을 따라 큐의 동작을 시뮬레이션하고, 해당 문서가 몇 번째로 인쇄되는지 정확히 계산합니다.
4. 시간 복잡도 분석
이 문제는 큐(Queue)를 사용하여 중요도를 비교하면서 문서의 인쇄 순서를 시뮬레이션하는 문제입니다. 각 테스트케이스에서 큐를 순회하며 문서를 처리하는 과정이 시간 복잡도에 영향을 미칩니다.
1. 큐에 문서를 삽입하고 꺼내는 작업
- 각 테스트케이스에서 큐에 N개의 문서가 들어가고,
popleft()연산과append()연산을 통해 문서를 꺼내거나 다시 넣습니다. deque의popleft()와append()연산은 각각 O(1)의 시간 복잡도를 가집니다.
2. 중요도 비교 작업
if any(current[1] < q[1] for q in queue)부분에서 현재 문서의 중요도와 나머지 문서들의 중요도를 비교합니다. 이는 O(N)에 가까운 시간이 걸립니다. 왜냐하면 한 번의 비교에서 큐에 남아있는 모든 문서들과 중요도를 비교해야 하기 때문입니다.
3. 총 시간 복잡도
- 각 문서를 한 번 꺼낸 후, 남아있는 문서들과 중요도를 비교합니다. 이 과정이 최대 N번 반복되며, 중요도 비교 작업은 N개의 문서에 대해 이루어지므로 O(N)입니다.
- 따라서, 한 테스트케이스에서 문서를 처리하는 전체 시간 복잡도는 O(N^2)에 가깝습니다.
4. 여러 테스트케이스에 대한 시간 복잡도
- 테스트케이스의 수를 T라고 하면, 총 시간 복잡도는 O(T * N^2)입니다.
- 문제에서 문서의 수 N은 최대 100개, 테스트케이스의 수 T도 여러 개 있을 수 있지만, N이 100 이하로 매우 크지 않으므로 O(N^2)의 시간 복잡도는 충분히 허용됩니다.
시간 복잡도 요약
- 한 테스트케이스에서 시간 복잡도: O(N^2)
- 여러 테스트케이스를 처리하는 시간 복잡도: O(T * N^2)
마무리
이 문제는 큐의 기본적인 동작에 우선순위 개념을 추가한 시뮬레이션 문제입니다. 주어진 조건을 따라 큐에서 문서를 처리하는 방법을 익히는 데 도움이 되는 문제로, 큐의 개념과 우선순위 처리를 함께 학습할 수 있습니다.
다음 포스팅부터는 프로그래머스의 자료 구조(스택, 큐, 덱)문제를 풀고 글을 작성할 것 같습니다.
많은 기대 부탁드립니다.
더 나은 개발자가 되기를 💪
