내 맴
[ BAEKJOON ] No. 1966 프린터 큐 본문
문제 )
https://www.acmicpc.net/problem/1966
1966번: 프린터 큐
문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를
www.acmicpc.net
[ 풀이 ]
list의 M번째 숫자가 몇번째로 출력되는지 알아내야함으로,
M번째 숫자의 위치를 알려주는 check라는 list를 도입해서 문제를 해결한다
✔ check : check[M]=1이고 나머지 값들은 모두 0이 되도록 initialize 한다
< 순서 >
- count=1
- queue가 다 사라질때까지 반복한다
1-1) queue의 제일 앞 값이 최댓값인 경우
if queue[0]이 M번째 값이었다면?
Ⅰ. count(비교횟수) 출력
else:
Ⅰ. count를 하나 늘려준다
Ⅱ. queue[0]을 제거한다.
Ⅲ. check[0]을 제거한다
1-2) queue의 제일 앞 값이 최대값이 아닌 경우
Ⅰ. queue[0]을 queue의 맨 뒤에 넣어준다
Ⅱ. check[0]을 check의 맨 뒤에 넣어준다
- python code
def Order(N,M,priority):
# initialize Check list
check=[0 for i in range(N)]
check[M]=1
count=1
while priority:
if priority[0]==max(priority):
if check[0]==1:
print(count)
break
else:
count+=1
priority.pop(0)
check.pop(0)
else:
priority.append(priority.pop(0))
check.append(check.pop(0))
testnum= int(input())
for i in range(testnum):
N,M=map(int, input().split())
priority=list(map(int,input().split()))
Order(N,M,priority)
'개발 공부 > Algorithm' 카테고리의 다른 글
[ BAEKJOON ] No. 1021 회전하는큐 (0) | 2020.04.18 |
---|---|
[ BAEKJOON ] No. 10866 덱 (0) | 2020.04.16 |
[ BAEKJOON ] No. 11866 요세푸스 문제 0 (0) | 2020.04.10 |
Greedy Algorithm - Fractional Knapsack Problem (0) | 2020.04.09 |
[ BAEKJOON ] No. 2164 카드2 (0) | 2020.04.09 |