백준 1021번 : 회전하는 큐(Python)

문제 링크 : https://www.acmicpc.net/problem/1021

문제

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

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

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

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

구현 방식

우선, 입력 값들을 받아낸다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split(' '))
l = list(map(int, input().split(' ')))

큐와 주어진 리스트를 동시에 연산하는 것보다 주어진 리스트 만으로 해결하고자 하였다.

선택할 수 있는 행동은 좌측으로 이동하냐, 우측으로 이동하냐 인데 더 최소한의 움직임을 택해야 한다.

우선 좌측으로 이동하는 함수이다.

def move_left(N, input_list, count):
    x = input_list[0]
    for i in range(len(input_list)):
        if input_list[i] >= x:
            input_list[i] -= x - 1
        else:
            input_list[i] += N - (x - 1)
    count += x - 1
    return N, input_list, count

주어진 리스트의 첫 번째 원소만큼 좌측으로 이동하는 함수이다.

결과적으로 리스트의 첫째 원소는 1 이 되고 나머지 원소는 x - 1만큼 shift 된다.

리스트의 첫 번째 원소보다 작은 원소는 우측으로 밀려나게 되는데 그 크기는 N - (x - 1)이다.

이에 따라 카운트도 x - 1만큼 추가된다.

마찬가지로 우측으로 이동하는 함수이다. 좌측과 유사하다.

def move_right(N, M, input_list, count):
    x = input_list[0]
    for i in range(len(input_list)):
        if input_list[i] < x:
            input_list[i] += N - x + 1
        else:
            input_list[i] -= x - 1
    count += N - x + 1
    return N, M, input_list, count

다음은 첫째 원소를 빼내는 함수이다. 첫째 원소를 소거하고 나머지 원소들을 각각 1을 빼주면 된다.

def remove_first(N, M, input_list):
    for i in range(M):
        l[i] -= 1
    N -= 1
    M -= 1
    input_list.remove(0)
    return N, M, input_list

주어진 M의 크기만큼 원소 추출을 반복해주어 카운트를 업데이트 시켜준다.

count = 0
for _ in range(M):
    if l[0] - 1 <= N - l[0] + 1:
        N, l, count = move_left(N, l, count)
        N, M, l = remove_first(N, M, l)
    else:
        N, M, l, count = move_right(N, M, l, count)
        N, M, l = remove_first(N, M, l)
print(count)