이 문제는 앞에서 구현해봤던 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)
deque
를 이용하여 양 방향에서 접근하는 방법을 사용해보자.
내가 생각한 알고리즘은 다음까지다.
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)
노력하자.