알고리즘 선택 트랙 [6일차]

<문제>

지민이는 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보다 작거나 같은 자연수이다.

출력

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

<문제 회고>

이 문제는 내가 처음 봤을 때 한번에 이해가 가지 않는 문제였다.

그래서 나는 이럴 때마다 문제를 있는 그대로 읽는 연습을 계속 해왔다.

그래서 내가 문제를 보고 있는 그대로 설명해보도록 하겠다.

#1. 두 수를 입력받는다.

#2. 마지막 수 만큼 뽑을 수를 입력받는다.

#3. 입력받은 수 만큼 반복문을 돌면서 다음과 같은 내용을 수행한다.

#3. (1) 입력받은 수와 큐의 첫번째 원소가 같을 때까지 다음과 같은 과정을 수행한다.

#3. (1) (1) 입력받은 수가 큐에서 자리잡고 있는 위치가 오른쪽으로 치우쳐져있는지 아닌지 확인한다.

#3. (1) (2) 입력받은 수가 큐에서 자리잡고 있는 위치가 오른쪽이라면 문제에서의 3번 과정을 수행한다.

#3. (1) (3) 입력받은 수가 큐에서 자리잡고 있는 위치가 왼쪽이라면 문제에서의 2번 과정을 수행한다.

#3. (2) "3.(1)의 과정"이 끝나고 나서는 큐에 첫번째 원소와 주어진 수가 같으므로 큐에 첫번째 원소를 제거한다.

#3. (2) 그리고 count를 하나 올린다.

#4. 이과정이 끝난다면 count를 출력한다.

from collections import deque
import sys
N,M = map(int,sys.stdin.readline().split())
numList = list(map(int,sys.stdin.readline().split()))
que = deque([n + 1 for n in range(N)])
cnt = 0
for num in numList:
    while que[0] != num:
        if que.index(num) <= len(que) // 2:
            que.append(que.popleft())
        elif que.index(num) > len(que) // 2:
            que.insert(0,que.pop())
        cnt += 1
    que.popleft()
print(cnt)

이 과정에서 보면 디큐가 사용된것을 볼 수 있다. 사실 이문제는 링 버퍼를 사용하는 문제다.

즉 이름에 알 수 있듯이 회전하는 큐라는 자료구조에 특징에 대해 물어본 문제이기 때문에 이 문제에서는 deque를 사용해야 한다.

우리가 여기서 알 수 있는 점은 deque라는 자료구조는 시간복잡도를 줄이기 위해서 쓰는 걸로 알고 있는데 이는 반만 정확한 이유이다.

deque를 이용하는 이유는 시간복잡도를 줄이는 뿐만 아니라 회전하는 특징을 이용할 때도 사용한다라는 특징이 있다.

(이 문제를 풀어보니...... 확실히 간단하고 있는 그대로 담담하게 이해하는 것이 가장 중요하다는 것을 깨달았다.....)