백준 1021 파이썬 풀이 - 바킹독 파이썬 문제 풀이

문제

0번째에 위치한 인덱스가 우리가 찾고 있는 숫자이면 삭제 및 출력한다. 

우리가 찾는 인덱스가 아닌 경우 왼쪽으로 이동하거나 오른쪽으로 이동시켜 큐의 위치를 변경한다.

양쪽으로 입력과 출력이 일어나므로 덱의 자료구조인 deque를 사용하면 좋습니다.

 

코드

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

n, m = map(int, input().split()) # 큐의 크기 n 과 뽑으려는 숫자의 개수 m
pos = list(map(int, input().split())) # 뽑아내려고 하는 수의 위치

q = deque(i for i in range(1, n+1)) # 큐 설정
cnt = 0 # 카운트 변수

for i in pos:
  while True:
    if q[0] == i:
      q.popleft()
      break
    else:
      if q.index(i) < len(q)/2:
        q.append(q.popleft())
        cnt += 1
      else:
        q.appendleft(q.pop())
        cnt += 1

print(cnt)

 

deque을 이용해서 양쪽에서 입력 및 삭제가 가능한 덱 자료구조를 이용했습니다.

1. q에 맨 앞에 있는 숫자가 찾는 숫자이면 popleft() 후 다음 숫자를 찾습니다.
2. 찾는 숫자가 아닌 경우 탐색을 진행합니다.

• q.index(i)를 통해 찾는 숫자의 인덱스를 구하고 이 값이 q의 절반의 크기보다 작은 경우는 중간 지점을 기준으로 왼쪽에 있는 것을 의미하므로 왼쪽으로 이동합니다. q.append(q.popleft())
• 이 값이 q의 절반의 크기보다 큰 경우는 중간 지점을 기준으로 오른쪽에 위치한 것이므로 오른쪽으로 이동합니다. q.appendleft(q.pop())