import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
for _ in range(N):
l, paper = map(int,input().split())
dq = deque(map(int,input().split(' ')))
done = 0
i = 0
while True :
if i+1 == len(dq):
if paper == 0:
print(done+1)
break
else:
dq.popleft()
paper -= 1
done += 1
i = 0
print('now : ', dq,paper)
if len(dq) == 1 :
print(done+1)
break
if dq[0] >= dq[i+1]:
i += 1
else:
dq.append(dq.popleft())
if paper == 0 :
paper = len(dq)-1
else:
paper -= 1
print(dq,paper)
i = 0
# 출력 예시
-- 입력 --
6 0
1 1 9 1 1 1
-- 출력 --
deque가 회전될 때 마다 혹은 popleft될 때 마다 paper의 위치 표시
deque([1, 9, 1, 1, 1, 1]) 5
deque([9, 1, 1, 1, 1, 1]) 4
now : deque([1, 1, 1, 1, 1]) 3
now : deque([1, 1, 1, 1]) 2
now : deque([1, 1, 1]) 1
now : deque([1, 1]) 0
-- 답 --
5
🗯️풀이 설명
고려했던 부분은 우선순위가 낮은 문서를 뒤로 보낼 때, 알고자하는 문서의 위치를 어떻게 변화시켜주는가 였다.
나는 paper 변수로 알고자하는 문서의 인덱스 값을 저장하여, 문서 dq의 순서가 변할 때 마다 paper 값을 변화시켜주었다.
작동 과정을 시각적으로 나타내보았다. 분홍색 하이라이트가 된 문서가 출력 순서를 알고자하는 문서이다. 즉, paper 변수이다.
0번 문서와 그 뒤의 문서의 중요도를 한 개씩 비교하면서 0번 문서보다 중요도가 큰 문서가 있을 경우 0번 문서를 맨뒤로 보내고,
0번 문서 보다 중요도가 큰 문서가 없을 경우 0번 문서를 프린트한다.
이 과정에서 분홍색 문서의 인덱스가 계속 변화하는 것을 알 수 있다. 따라서 paper = = 0 이 될 때 까지 알고리즘이 작동한다.
👀 반례
2
9 3
4 3 2 2 3 5 2 1 3
4 1
2 1 4 3
# 7
# 4
1
100 0
1 2 3 4 5 6 7 8 9 2 2 3 4 5 6 7 8 9 2 2 3 4 5 6 7 8 9 2 2 3 4 5 6 7 8 9 2 2 3 4 5 6 7 8 9 2 2 3 4 5 6 7 8 9 2 2 3 4 5 6 7 8 9 2 2 3 4 5 6 7 8 9 2 2 3 4 5 6 7 8 9 2 2 3 4 5 6 7 8 9 5 5 5 5 5 5 5 5 5 5
# 100
💡다른 풀이
뿌기님의 풀이가 더 맘에 들어서 가지고 왔당
from collections import deque
t = int(input())
for _ in range(t):
n, m = map(int, input().split())
pop_num = []
queue = deque([i+1 for i in range(n)])
find_num = queue[m]
imp_q = deque(map(int, input().split()))
while True:
if len(imp_q) == 0 :
break
max_idx = imp_q.index(max(imp_q))
if max_idx != 0:
queue.rotate(-1)
imp_q.rotate(-1)
continue
elif max_idx == 0:
pop_num.append(queue.popleft())
imp_q.popleft()
continue
for num in pop_num :
if find_num == num :
print(pop_num.index(num) + 1)
deque 에 rotate 기능이 있는지 덕분에 알게 되었다 ..ㅎ 언니는 내가 코드 가져온거 모르겠지....ㅎ
'🏷️CS > Algorithm' 카테고리의 다른 글
[코테 스터디] 2주차 : DFS/BFS (1) | 2024.06.17 |
---|---|
[코테 스터디] 1주차 : 자료구조 / 이진탐색 (1) | 2024.06.10 |
[백준] 구현 2941 / 1193 / 2775 (1) | 2023.05.13 |
[백준] 구현 1157 / 4673 / 1316 (0) | 2023.05.09 |
코테에 사용하기 좋은 라이브러리 기능 (0) | 2023.04.30 |