📜 문제 이해하기
지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.
지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.
첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.
큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.
💡 문제 재정의
회전하는 큐에서 데이터를 찾았을 때 가장 최소로 하는 연산을 출력하라.
✏️ 계획 수립
회전하는 큐는 항상 왼쪽 데이터를 POP하고 오른쪽에 데이터를 추가한다. 하나씩 찾아보면서 데이터를 발견하면 데이터를 추가하지 않고 탐색을 마친다. 만약 탐색 횟수가 큐의 크기의 2분의 1보다 크다면 연산의 수를 큐의 크기 - 연산의 수 + 1로 바꿔준다. 이는 최소 연산이 큐의 2분의 1보다 항상 크지 않기때문이고 만약 커진다면 이는 반대 방향이 더 최소 연산을 가진다는 뜻이다. 따라서 N - cnt + 1로 갱신해준다.
💻 계획 수행
from collections import deque
import sys
if __name__ == '__main__':
deq = deque()
N, M = map(int, sys.stdin.readline().split())
find_nums = list(map(int, sys.stdin.readline().split()))
cnt_sum = 0
for i in range(1, N+1):
deq.append(i)
for _ in range(M):
find_num = find_nums.pop(0)
cnt = 0
while True:
num = deq.popleft()
if num == find_num:
N -= 1
break
deq.append(num)
cnt += 1
if cnt > N // 2:
cnt = N - cnt + 1
cnt_sum += cnt
print(cnt_sum)🤔 회고
원래는 회전하는 큐 두개를 만들어서 왼쪽 회전, 오른쪽 회전 큐를 모두 검색하고 최소 연산을 찾으려고 했지만 이는 너무 시간 낭비라고 생각했고 큐 하나로 구현할 수 있는 방법을 생각했다.
