[백준-Python] 회전하는 큐 : 1021번

🥈 Silver3

https://www.acmicpc.net/problem/1021

 

 

 

 

✅ 정답풀이

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

n, m = map(int, input().split())
num_list = list(map(int, input().split()))


# 2번과 3번 중 어느 방법을 결정할지-> 중간 인덱스를 기준으로 해당 index가 가까운쪽으로
q = deque([i for i in range(1, n + 1)])


result = 0
for num in num_list:

    while True:
        # 맨앞 요소가 빠져나갈수있는지 확인
        if q[0] == num:
            q.popleft()
            break

        idx = q.index(num)
        mid = len(q) // 2
        if idx <= mid:
            # 2번 과정
            q.append(q.popleft())
        else:
            # 3번 과정
            q.appendleft(q.pop())
        result += 1

print(result)

#34160	64

메모리	실행시간
34160	64

 

 

이 문제는 문제를 이해하는데 오래걸린 문제지, 생각보다 접근방식은 쉬웠던것 같다.

3번과정을 통해 맨오른쪽 요소가 맨앞으로 올때만 카운트를 하고, 뽑아내는건 queue처럼 맨앞에서만 뽑는 1번과정을 통해 일어나는것인데

맨뒤에서만 있어도 바로 요소를 꺼낼수 있다고 생각해 카운트를 하지 않다보니 문제 이해에 오랜시간이 소요되었다.

 

2,3번 방법중 어느 방법을 사용할지 결정하고 카운트만 해주면 되기 때문에, 어떤방법을 사용해야할지가 포인트인데 

뽑아내고 싶은 요소가 가운데를 기점으로 왼쪽에 가까우면 2번, 오른쪽에 가까우면 3번을 선택하면 되기 때문에

뽑아야하는 idx를 구하고, mid 인덱스를 구한다음 비교해주면 된다!