[Python] 백준 1021번 문제 풀이 - 회전하는 큐

문제 링크

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

문제 이해

이 문제는 N이 주어지면 [1, 2, …, n-1, n]이 주어지고

두번째 줄에 주어지는 숫자를 3개의 연산을 통해 빼내는 최소 횟수를 구하는 문제입니다.

연산은 다음이 있습니다.

1. 첫번째 원소를 뽑아낸다. [1, 2, …, n-1, n] → [2, 3, …, n-1, n]
2. 왼쪽으로 한칸 이동시킨다. [1, 2, …, n-1, n] → [2, 3, …, n, 1]
3. 오른쪽으로 한칸 이동시킨다. [1, 2, …, n-1, n] → [n, 1, …, n-2, n-1]

아이디어

우선 이 문제에서 원소를 뽑아내는 것은 1번 연산밖에 없습니다.

그래서 가장 최적의 2,3번 연산을 수행하여 최소 횟수로 원소를 잘 뽑아내면 되는 것입니다.

최적의 2,3번 연산을 수행하는 방법은 뽑고자 하는 원소의 인덱스를 출력하고 그 인덱스가 0에 가까운지 배열의 길이에 가까운지 비교해서 연산을 돌립니다.

예를 들어 [1,2,3,4,5]에서 3을 빼려고 할때

왼쪽으로 이동한다면 [1,2,3,4,5] → [2,3,4,5,1] → [3,4,5,1,2] 로 2번 이동한 후 첫번째 원소를 빼고,

오른쪽으로 이동한다면 [1,2,3,4,5] → [5,1,2,3,4] → [4,5,1,2,3] → [3,4,5,1,2]로 3번 이동한 후 첫번째 원소를 뺍니다.

그래서 왼쪽으로 이동하는 것이 최소 이동횟수인것입니다.

그리고 뽑으려는 숫자가 0번째 인덱스에 있다면

바로 뽑으면 됩니다.

그래서 정리하면

1. 뽑으려는 숫자를 배열에 저장해둔다.
2. 반복문을 통해 배열을 돌며 숫자의 인덱스를 구하고 0번째 인덱스면 바로 뽑고 해당 반복을 끝낸다.
3. 해당 인덱스 - 0과 해당 인덱스 - len(q)를 통해 더 최적의 연산을 구합니다.
4. 왼쪽이 더 작다면 2번연산을 인덱스 차이만큼 돌리고 오른쪽이 더 작다면 3번연산을 인덱스 차이만큼 돌립니다.
   1. 2번연산을 돌리는 함수는 cnt를 1 증가시키고, 맨 앞의 원소를 빼서 큐의 맨 뒤에 추가하는 연산을 합니다.
   2. 3번 연산을 돌리는 함수는 cnt를 1 증가시키고, 맨 뒤의 원소를 빼서 큐의 맨 앞에 추가하는 연산을 합니다.
5. 돌린 횟수를 출력합니다.

시간복잡도

뽑아내야 하는 숫자의 반복문을 돌리니 O(M)이 걸립니다.

인덱스를 구하는 연산은 큐의 길이만큼 도니 O(N)이 걸립니다.

그리고 빼는 2번연산과 3번연산은 원소를 pop하고 append 하는 연산만 수행하기 때문에 O(1)이 걸립니다.

그것을 인덱스 - 0 혹은 인덱스 - 큐의 길이 만큼 수행하니 O(N/2) 가 걸립니다.

반복문 내에서 인덱스 계산하고 연산하니 전체 시간복잡도는 O(MXN)이 나오게 됩니다.

N과 M의 최대값은 50이니

O(NXM) → 2500 가능합니다.

코드 구현

이 아이디어를 코드로 구현하면 다음과 같습니다.

import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())
# 뽑아야 하는 수 리스트
num_list = map(int, input().split())
# 회전 하는 큐 1 ~ n
q = deque()
for i in range(1, n+1):
    q.append(i)

# 횟수 저장 변수
cnt = 0

# 두번째 연산
def second_command():
    global cnt
    x = q.popleft()
    q.append(x)
    cnt += 1

# 세번째 연산
def third_command():
    global cnt
    x = q.pop()
    q.appendleft(x)
    cnt += 1

# 뽑아내야 하는 수 반복문
for num in num_list:
    # 뽑아내야 하는 수가 0이면 바로 뽑아내고 해당 반복 종료
    if q[0] == num:
        q.popleft()
        continue
    # 0과의 거리와 끝과의 거리 저장
    left = abs(q.index(num) - 0)
    right = abs(q.index(num) - len(q))

    # 0과의 거리가 가깝다면
    if left <= right:
        # 2번째 연산 left 거리만큼 반복
        for _ in range(left):
            second_command()
        q.popleft()
    # 끝과의 거리가 가깝다면
    else:
        # 3번째 연산 right 거리만큼 반복
        for _ in range(right):
            third_command()
        q.popleft()
# 횟수 출력
print(cnt)