1966번: 프린터 큐
여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 큐를 이용하여 문제의 조건을 잘 작성해주면 정답을 받을 수 있는 문제였습니다.
파이썬에서 큐를 이용하기 위해서는 from collections import deque 코드의 윗부분에 첨가합니다.
먼저 입력받은 n개의 숫자들을 중요도와 묶어서 큐에 append 해줍니다. 그 후 큐를 조회하면서 뒤쪽에 더 높은 우선순위를 가진 작업이 존재할 경우 큐에서 popleft()를 해준 후 뒤쪽에 append 해줍니다. 반면 뒤쪽에 더 높은 우선순위를 가진 작업이 존재하지 않다면 바로 출력을 해줍니다. 이때 출력을 하기 전 popleft를 해준 후 popleft 된 작업의 번호와 입력받은 원래의 작업들 중에서 m번째 존재하는 값이 값다면 count를 출력해주고 값이 같지 않다면 count를 하나 증가시키는 것으로 해결합니다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
from collections import deque
tc = int(input())
for i in range(tc):
q = deque()
n, m = map(int, input().split())
priority = list(map(int, input().split()))
a = 1
for p in priority:
q.append((a, p)) # 우선순위와 쌍으로 결합하여 큐에 append한다.
a += 1
i = 0
count = 1
while i < len(q):
check = True
for j in range(i, len(q)): # 뒤쪽에 더 높은 우선순위를 가진 작업을 찾는다
if q[i][1] < q[j][1]:
a, p = q.popleft()
q.append((a, p))
check = False
break
if not check: # 더 높은 우선순위를 가진 작업이 없는 경우
i = 0
else: # 더 높은 우선순위를 가진 직업이 존재하는 경우
a, p = q.popleft()
if a == 1 + m: # m번째 작업이 popleft한 작업과 같은 경우 count를 출력
print(count)
break
else: # m번째 작업이 popleft한 작업과 다른 경우 count를 하나 증가시켜줌
count += 1
i = 0
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 1475: 방 번호(Python) (0) | 2021.02.03 |
|---|---|
| 백준 알고리즘 7568: 덩치(Python) (0) | 2021.02.03 |
| 백준 알고리즘 1316: 그룹 단어 체커(Python) (0) | 2021.02.02 |
| 백준 알고리즘 1152: 단어의 개수(Python) (0) | 2021.02.02 |
| 백준 알고리즘 2739: 구구단(Python) (0) | 2021.02.02 |