[알고리즘] 백준 1021 회전하는 큐

문제링크

• https://www.acmicpc.net/problem/1021

문제 설명

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐의 크기와 뽑아내려는 수의 위치가 주어질 때 2와 3를 연산하는 최소 횟수를 구하라.

주제

• 큐

난이도

• 중상

풀이 전 생각한 것

1. 뽑고자 하는 인덱스의 위치에 따라 원소가 오른쪽으로 이동할 지, 왼쪽으로 이동할 지 결정해야햄!!

풀이

import sys
from collections import deque
size, num = map(int, sys.stdin.readline().split())
idx = list(map(int, sys.stdin.readline().split()))

# 입력값으로 주어진 사이즈에 맞춰 큐를 생성한다.
# (추출해야하는 인덱스을 큐에 담긴 숫자와 비교하며 진행)
queue = deque([i for i in range(1, size+1)])
count = 0

for i in idx:
    while True:
        # 뽑아내려는 인덱스와 현재 큐의 인덱스가 동일하다면 pop 진행
        if i == queue[0]:
            queue.popleft()
            break

        # 찾고자하는 인덱스의 위치가 중간 인덱스보다 작다면 앞 -> 뒤로 원소를 보내준다.
        if queue.index(i) <= len(queue) // 2:
            while i != queue[0]:
                queue.append(queue.popleft())
                count += 1

        # 찾고자하는 인덱스의 위치가 중간 인덱스보다 크다면 뒤 -> 앞으로 원소를 보내준다.
        else:
            while i != queue[0]:
                queue.appendleft(queue.pop())
                count += 1

print(count)

풀이 방법

1. 데크를 이용하여 임의로 큐의 사이즈 만큼 인덱스와 동일한 일련의 번호를 저장한다.
2. 반복문을 돌며 큐의 첫번째 인덱스 값이 추출하고자 하는 인덱스와 동일하면 pop()을 진행한다.
3. 만약, 첫번째 인덱스 값과 동일하지 않다면 동일해질 때까지 원소들을 이동시킨다.
   이때, 찾고자하는 인덱스가 중간 인덱스보다 작다면 원소를 왼쪽에서 오른쪽으로,
   중간 인덱스보다 크다면 오른쪽에서 왼쪽으로 이동시켜준다.

문제를 풀고 알게된 개념 및 소감

• 막연히 for문과 while문이 많으면 비효율적이라고 생각했지만 반대로 필요한 부분들만 집중적으로 반복할 수 있게 해줘서 더 효율적으로 코드를 짤 수 있었다. 코드를 짤 때 넓게 바라보는 법을 알고리즘 공부를 하며 배운다.