[백준 1021] 회전하는 큐 (Python)

바킹독 덱 강의 연습 문제. 스택이나 큐와 달리 앞뒤에서 모두 삽입, 삭제가 가능하다는 점만 다르다.

회전하는 큐라는 이름에서부터 덱을 떠올릴 수 있다. 그렇지만 강의에서 배운 배열 방식으로는 문제를 풀 방법이 떠오르지 않아서 구글링을 해보니까 파이썬의 collections 모듈에 deque 클래스가 있다.

덱에 들어있는 숫자가 있는 인덱스가 덱의 앞과 가까운지, 뒤와 가까운지를 판단해서 회전시키다가 맨 앞에 오면 제거한다.

🦾 배운 점

• deque 클래스 사용법
  • 앞에 추가는 appendleft()
  • 뒤에 추가는 append()
  • 앞에서 삭제는 popleft()
  • 뒤에서 삭제는 pop()
  • 회전시키는 rotate()도 있다.
    인자가 양수면 오른쪽으로, 음수면 왼쪽으로 회전한다.
• 지금까지 배열의 원소를 각각 int로 변환할 때 반복문을 사용했는데, map() 함수로 int 변환을 먼저 하고 다시 list()로 묶어주면 바로 리스트가 딱 나온다는 걸 알게 됐다...
  예) a = list(map(int, input().split()))

from collections import deque	# 덱 컨테이너 추가

n, m = map(int, input().split())	# 최댓값 n, 바꿀 자료의 개수 m 입력받기 (사실 m은 쓸모가 없다.)
d = deque(range(1, n + 1))			# deque 만들기
a = list(map(int, input().split()))	# 제거할 수 목록 입력받기

count = 0		# 회전 연산 수를 저장할 변수
for num in a :	# 제거할 수의 길이만큼 반복
	if d.index(num) <= len(d) // 2 :	# 덱에서 제거할 수가 들어있는 인덱스가 시작과 가까우면
		while d[0] != num :				# 덱의 맨 앞에 있는 수가 제거할 수가 아닌 때까지
			d.rotate(-1)				# 덱을 왼쪽으로 회전
			count += 1					# count 증가
	else :								# 덱에서 제거할 수가 들어있는 인덱스가 끝과 가까우면
		while d[0] != num :				# 덱의 맨 앞에 있는 수가 제거할 수가 아닌 때까지
			d.rotate(1)					# 덱을 오른쪽으로 회전
			count += 1					# count 증가
    d.popleft()							# 맨 앞으로 이동한 제거할 수 삭제
print(count)	# 결과 출력