🗂️ 문제
링크: https://www.acmicpc.net/problem/1966
💡 접근법
제일 왼쪽의 값을 쉽게 꺼내기 위해 deque를 사용한다.
문서가 몇 번째로 인쇄되는지 횟수를 세기 위해 인덱스를 저장해야 한다. 이를 위해 queue에 튜플 형식으로 (인덱스, 중요도)를 저장한다.
while()문을 통해 큐에서 왼쪽에 위치한 값을 하나씩 꺼내고, 만약 그 다음 값들 중 현재 값보다 중요도가 높은 문서가 있다면 다시 큐에 현재 값을 삽입한다.
이때 인쇄가 될 경우 카운트 횟수를 증가시켜야 한다. 따라서 큐에서 현재 값을 꺼낼 때 카운트를 1 증가시키고, 만약 현재 값보다 중요도가 큰 문서를 발견하여 현재 값을 다시 큐에 삽입하게 되면 카운트를 1 감소시킨다.
target에 궁금한 문서를 저장해 두었다가, 큐에서 target이 빠져나갔을 경우, 즉 인쇄됐을 경우 while문을 빠져나온다.
😎 내 코드
import sys
from collections import deque
cnt = int(sys.stdin.readline())
for _ in range(cnt):
N, M = map(int, sys.stdin.readline().split())
que = list(map(int, sys.stdin.readline().split()))
queue = deque()
for i, q in enumerate(que):
queue.append((i, q)) # (인덱스, 중요도)
target = queue[M]
count = 0
while(queue):
q = queue.popleft()
count += 1
for i in range(len(queue)):
if queue[i][1] > q[1]:
queue.append(q)
count -= 1
break
if target not in queue:
break
print(count)
✅ 정답 확인
'Algorithm > Baekjoon' 카테고리의 다른 글
[BFS] 백준 #2468 안전 영역 - Python (0) | 2024.05.30 |
---|---|
[BFS] 백준 #7562 나이트의 이동 - Python (0) | 2024.05.26 |
[DFS] 백준 #2667 단지번호붙이기 - Python (0) | 2024.05.18 |
[BFS] 백준 #1325 효율적인 해킹 - Python (0) | 2024.05.14 |
[그래프] 백준 #1753 최단경로 - Python (0) | 2024.05.11 |