10866번

이 문제는 앞에서 구현해봤던 stack, Queue와 기본적인 틀이 같다.

import sys
input = sys.stdin.readline

n = int(input())
deque = []

for _ in range(n):
    inst = list(input().split())
    
    if inst[0] == 'size':
        print(len(deque))
        
    elif inst[0] == 'empty':
        empty = 0 if deque else 1
        print(empty)
    
    elif inst[0] == 'front':
        front = deque[0] if deque else -1
        print(front)
        
    elif inst[0] == 'back':
        back = deque[-1] if deque else -1
        print(back)
        
    elif inst[0] == 'pop_front':
        if deque:
            pf = deque.pop(0)
            print(pf)
        else:
            print(-1)
            
    elif inst[0] == 'pop_back':
        if deque:
            pb = deque.pop()
            print(pb)
        else:
            print(-1)
            
    elif inst[0] == 'push_front':
        int_front = inst[1]
        deque.insert(0, int_front)
        
    elif inst[0] == 'push_back':
        int_back = inst[1]
        deque.append(int_back)

1021번

deque를 이용하여 양 방향에서 접근하는 방법을 사용해보자.

내가 생각한 알고리즘은 다음까지다.

1. 큐의 크기 n과 뽑아내려고 하는 수의 개수 m을 입력받는다.
2. 뽑아내려고 하는 수의 위치를 입력값으로 받는다.
3. 문제 속 2, 3번을 수행하면 카운트 올린다.
4. 큐의 첫 인덱스가 뽑아내려고 하는 수의 위치와 같다면 1번 수행

2번, 3번 연산은 append 와 popleft, appendleft, pop 등을 사용해서 작성하면 될 것 같은데..

n = 10, m = 3인 경우
뽑아내려고 하는 원소의 위치가

2 9 5

와 같은 경우에는 어떻게 접근해야하는 지 떠올리기 어려웠다.

그래서 다른 분의 코드를 확인한 결과 이진 검색 알고리즘을 적용하여 문제에 접근한 것을 알 수 있었다.

else:
            if dq.index(i) < len(dq)/2:  # 뽑아내려는 수의 위치 인덱스가 dq의 길이를 반으로 나눈것보다 작을때는 왼쪽으로 움직여야 최소
                while dq[0] != i:   # dq의 첫번째 인덱스가 i와 같아질때까지 반복
                    dq.append(dq.popleft())  
                    count += 1
            else:   # 뽑아내려는 수의 위치 인덱스가 dq의 길이를 반으로 나눈것보다 클때는 오른쪽으로 움직여야 최소
                while dq[0] != i:
                    dq.appendleft(dq.pop())  
                    count += 1

참고
[Algorithm] 백준 1021번 회전하는 큐(파이썬) - goplanit.log

분명 공부했던 개념인데.. 실제로 적용을 떠올리지 못해 너무 아쉬운 문제였다.
다시 한 번 블로그에 정리하면서 내용을 다시 머리에 새겨야겠다..

최종 코드

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())    # 큐의 크기 n과 뽑아내려고 하는 수의 개수 m을 입력값으로 받기
position = list(map(int, input().split()))  # 뽑아내려는 수의 위치를 입력값으로 받기
dq = deque([i for i in range(1, n+1)])  # deque([1, 2, 3,...,n])

count = 0   # 2, 3번 수행하면 카운트 올리기
for i in position:  # 뽑아내려는 수의 위치 하나씩 반복문 돌리기
    while True:     # 뽑을 때까지 계속 돌리기
        if dq[0] == i:  # dq의 첫인덱스가 뽑아내려는 수의 위치와 같다면 1번 수행
            dq.popleft()
            break
        else:
            if dq.index(i) < len(dq)/2:  # 뽑아내려는 수의 위치 인덱스가 dq의 길이를 반으로 나눈것보다 작을때는 왼쪽으로 움직여야 최소
                while dq[0] != i:   # dq의 첫번째 인덱스가 i와 같아질때까지 반복
                    dq.append(dq.popleft())  
                    count += 1
            else:   # 뽑아내려는 수의 위치 인덱스가 dq의 길이를 반으로 나눈것보다 클때는 오른쪽으로 움직여야 최소
                while dq[0] != i:
                    dq.appendleft(dq.pop())  
                    count += 1
print(count)

노력하자.