백준 1021번 회전하는 큐 - Python

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

이번 문제는 큐를 이용하여 푸는 문제다.

풀이

1. 양방향 순환 큐를 만들어서 최소한으로 순환하여 값을 뽑아내야한다.
2. 왼쪽, 오른쪽을 비교하여 더 가까운 쪽으로 순환해야 최솟값을 구할 수 있다.( 큐의 길이에서 인덱스 값을 빼주어 더 가까운 쪽을 찾으면 된다. )
3. 뽑은 수는 큐에서 없애야 한다.
4. append 함수를 사용하여 추가하고, del 함수를 사용하여 추가한 요소는 지워주었다.
5. 뽑고 남은 수들을 또 순환하여 다음에 뽑을 수를 구한다.

해답

n, m = map(int,input().split())  # [10,3]
targets = list(map(int,input().split())) # [2,9,5]
queue = [ i for i in range(1, n+1)] # [1,2,3,4,5,6,7,8,9,10]
result = 0

for i in range(m):
    queue_len = len(queue) # 10
    index = queue.index(targets[i]) 2 = 1 / 5 = 4 / 9 = 8
    # print(index) # targets의 위치값 구하기

    if index < queue_len - index : # 구하고자 하는 위치가 앞쪽에 있는 경우 앞으로 이동이 유리하다
        while True : 
            if queue[0] == targets[i] :
                del queue[0]
                break
            else :
                queue.append(queue[0]) # 첫번째 요소를 맨 뒤에 추가하고, 첫번째 요소는 지워 이동한다.
                del queue[0]
                result += 1 # 이동횟수 + 1
    else : 
        while True : # 구하고자 하는 위치가 뒤쪽에 있는 경우 뒤로 이동이 유리하다
            if queue[0] == targets[i] :
                del queue[0]
                break
            else :
                queue.insert(0,queue[-1]) # 마지막 요소를 첫번째로 넣어주고 마지막 요소는 지운다.
                del queue[-1]
                result += 1 # 이동횟수 + 1
print(result)

이 문제는 큐를 이용하여 풀기때문에, 큐에 대한 성질을 조금 더 확실하게 이해할 수 있었다. deque를 사용하지 않고 리스트의 del 함수를 사용하여 풀어보았다.