저별이의 초보 코딩

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

출력

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

입력 예시

10 3
1 2 3

출력 예시

0

코드 및 설명

from collections import deque
import sys
#where=list()
n,m=map(int,sys.stdin.readline().split())
line=deque([i+1 for i in range(n)])
where=list(map(int,sys.stdin.readline().split()))
answer=0
for i in where:
    

    while True:
        if line[0]==i:
            line.popleft()
            break
        else:
            if line.index(i)<=len(line)//2:
                line.rotate(-1)
                answer+=1
            else:
                line.rotate(1)
                answer+=1
        
print(answer)

이 문제는 문제를 이해하는 것이 중요하다고 생각이 든다. 나 역시도 이 구조가 어떻게 하는 방식인지는 이해했지만 방식을 어떻게 활용해야 하는지 감을 못잡았기 때문이다. 일단 문제를 이해해보도록 하자.

3가지 연산을 할 수 있다고 한다.

첫번째 연산은 단순히 앞에 있는 숫자를 뽑아낸다고 생각하면 된다. 즉 맨 앞에 있는 숫자가 원하는 위치의 숫자일 때를 의미한다. 그러면 다른 숫자의 이동 없이 뽑아내면 된다. 그렇게 되면 이 문제에서 최종적으로 출력하는 이동 정도 값에는 영향이 없다.

두번째 연산과 세번째 연산에 대한 이해를 해보도록 하자. 먼저 방식을 이해해보자면 배열에서 각각을 왼쪽으로 이동하게 되면 맨 앞에 있는 숫자는 맨 뒤로 이동한다. 세번째 연산은 그 반대이므로 각각 오른쪽으로 이동한 뒤 가장 뒤에 있는 값은 맨 앞으로 오게 한다. 여기서 이동할 때마다 이동한 정도를 더해주어야 한다. 

그럼 코드에 대해서 보도록 하자.

이 문제는 앞뒤로 뽑고 해주어야 하므로 덱 문제이다. 그래서 deque로 리스트를 만들어 주었고 입력 받는 것 역시 리스트 형태로 구분해서 받도록 해주었다. 이후 for문으로 입력받은 값이 반복되는 동안 안의 코드를 실행하도록 하였는데 맨 앞의 값과 해당 값이 같으면 바로 뽑고 break를 걸었고 아니라면 이제 길이를 재서 중간보다 작다면 2번 연산, 아니라면 3번 연산을 하도록 해주었다. 

여기서는 rotate라는 명령어를 활용하였다. 단계별 풀어보기의 이 문제 앞에 있는 덱 문제에서는 popleft라는 것을 통해서 숫자를 뽑아내는 방식을 택했다. 이 문제도 가능하다. 뽑아서 가장 뒤로 추가해주면 되니까. 그렇게 되면 line.append(line.popleft()) 이렇게 해주면 될것이다. 반대의 경우에도 line.appendleft(line.pop())를 이용해 해주게 되면 똑같이 실행된다. 

이 방식은 뽑고 다시 추가를 해줘야 한다는 점에서 코드 길이는 변화는 없지만 복잡해보인다. 뽑고 알아서 추가해주는 것을 대신 해주는 것이 rotate라는 명령어이다. 이제 1을 넣게 되면 각각 오른쪽으로 이동해 맨 뒤에 값이 맨 앞으로 오게 된다. -1을 넣어주면 반대로 왼쪽으로 이동해 맨 앞의 값이 맨 뒤에 값으로 이동할 것이다. 좀 더 편하게 해주는 것이라고 볼 수 있다.

두가지 방식을 해보면서 덱의 개념을 이해해보는게 좋을 것 같다는 생각이 든다.