[알고리즘] 백준 1021 회전하는 큐
문제링크
문제 설명
지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.
- 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
- 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
- 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.
큐의 크기와 뽑아내려는 수의 위치가 주어질 때 2와 3를 연산하는 최소 횟수를 구하라.
주제
- 큐
난이도
- 중상
풀이 전 생각한 것
- 뽑고자 하는 인덱스의 위치에 따라 원소가 오른쪽으로 이동할 지, 왼쪽으로 이동할 지 결정해야햄!!
풀이
import sys
from collections import deque
size, num = map(int, sys.stdin.readline().split())
idx = list(map(int, sys.stdin.readline().split()))
# 입력값으로 주어진 사이즈에 맞춰 큐를 생성한다.
# (추출해야하는 인덱스을 큐에 담긴 숫자와 비교하며 진행)
queue = deque([i for i in range(1, size+1)])
count = 0
for i in idx:
while True:
# 뽑아내려는 인덱스와 현재 큐의 인덱스가 동일하다면 pop 진행
if i == queue[0]:
queue.popleft()
break
# 찾고자하는 인덱스의 위치가 중간 인덱스보다 작다면 앞 -> 뒤로 원소를 보내준다.
if queue.index(i) <= len(queue) // 2:
while i != queue[0]:
queue.append(queue.popleft())
count += 1
# 찾고자하는 인덱스의 위치가 중간 인덱스보다 크다면 뒤 -> 앞으로 원소를 보내준다.
else:
while i != queue[0]:
queue.appendleft(queue.pop())
count += 1
print(count)
풀이 방법
- 데크를 이용하여 임의로 큐의 사이즈 만큼 인덱스와 동일한 일련의 번호를 저장한다.
- 반복문을 돌며 큐의 첫번째 인덱스 값이 추출하고자 하는 인덱스와 동일하면 pop()을 진행한다.
- 만약, 첫번째 인덱스 값과 동일하지 않다면 동일해질 때까지 원소들을 이동시킨다.
이때, 찾고자하는 인덱스가 중간 인덱스보다 작다면 원소를 왼쪽에서 오른쪽으로,
중간 인덱스보다 크다면 오른쪽에서 왼쪽으로 이동시켜준다.
문제를 풀고 알게된 개념 및 소감
- 막연히 for문과 while문이 많으면 비효율적이라고 생각했지만 반대로 필요한 부분들만 집중적으로 반복할 수 있게 해줘서 더 효율적으로 코드를 짤 수 있었다. 코드를 짤 때 넓게 바라보는 법을 알고리즘 공부를 하며 배운다.
Author And Source
이 문제에 관하여([알고리즘] 백준 1021 회전하는 큐), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ysong0504/알고리즘-백준-1021-회전하는-큐저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)