[Algorithm] 백준 1021 - 회전하는 큐 in Python(파이썬)

💡 백준 1021:

덱 기본 구조 활용

🌱 코드 in Python

알고리즘: Deque

import sys

n, m = map(int, sys.stdin.readline().split())
idx = list(map(int, sys.stdin.readline().split()))
d = [i for i in range(1, n + 1)] # 원소 위치 기록
ret = 0
for i in range(m):
	for j in range(len(d)): # 찾으려는 원소의 위치가 현재 어디에 있는지 확인
		if idx[i] == d[j]:
			break
	if j <= len(d) / 2: # 현재 위치가 현재 배열의 길이 / 2 보다 작거나 같으면
		while idx[i] != d[0]: # 첫번째 원소가 찾으려는 원소가 아닌 동안
			d.append(d.pop(0)) # 앞에서 뽑아 뒤에 넣는 2번 연산 실행
			ret += 1
	else: # 현재 위치가 현재 배열의 길이 / 2 보다 크면
		while idx[i] != d[0]: # 첫번째 원소가 찾으려는 원소가 아닌 동안
			d.insert(0, d.pop()) # 뒤에서 뽑아 앞에 넣는 3번 연산 실행
			ret += 1
	d.pop(0) # 첫번째 원소가 찾으려는 원소이면 pop
print(ret) # 최종 연산 횟수 출력

이번 문제는 덱 자료구조를 활용하면 쉽게 풀 수 있는 문제였다
42서울 푸쉬스왑 과제에서 원형배열을 가지고 스택을 만들었어서 조금 반가운 문제였음!

맨 첫번째 원소가 내가 찾으려는 원소일 때는 pop을 하고
아닐 경우 원소들을 왼쪽으로, 또는 오른쪽으로 돌려 찾으려는 원소를 가장 앞에 배치하게끔 하는 문제였다
이때 어느 방향으로 돌려야 가장 최소 연산 갯수가 나오는지 분기를 나누어주는 것이 주요 문제였다

배열의 인덱스는 0부터 시작하기 때문에 현재 위치가 배열의 길이 / 2를 한 것보다 작거나 같을 경우 왼쪽, 아닐 경우 오른쪽으로 돌리는 게 더 적은 연산을 하게 된다
또한, 원소를 pop하면서 원소의 위치가 바뀌기 때문에 해당 원소의 위치를 매 순간 다시 잡아줘야 한다

나는 for문으로 돌려서 찾았는데
d.index(num)과 같이 index함수를 활용하여 해당 원소의 위치를 알 수 있다!

🧠 기억하자

1. index 함수
   • 배열에서 인자로 넘겨준 원소가 몇번째 index에 있는지 반환해주는 함수

백준 1021 바로가기