[자료구조/큐] 백준 1021 회전하는 큐 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1021번: 회전하는 큐

 

 

 

2. 문제 풀이

1번 연산) 첫 번째 항목 꺼내기
2변 연산) 왼쪽으로 한 칸씩 이동
3번 연산) 오른쪽으로 한 칸씩 이동

 회전하는 큐를 구현하고, 2 또는 3번 연산을 최소로 사용해서 특정 항목을 꺼내는 문제입니다.

 

2022.02.10 - [Algorithm] - [Algorithm] 큐(Queue), 선입선출 줄서기 자료구조

[Algorithm] 큐(Queue), 선입선출 줄서기 자료구조

 '원형 큐'와 같이 빙글빙글 돌아가며 항목을 꺼내야 합니다. 문제에 나온 것처럼 리스트를 한 칸씩 밀고 당기려면 상당한 연산시간이 필요합니다.

 그 대신 항목을 꺼낼 포인터만 앞뒤로 이동하면, 불필요한 연산을 크게 줄일 수 있습니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
N, M = map(int, input().split())
queue = list(range(1, N+1))
numlist = list(map(int, input().split()))

res = 0  # 2번, 3번 연산횟수
pointer = 0  # 큐 포인터
for idx, x in enumerate(numlist):
    # 왼쪽으로 탐색
    left = 0 # 2번 연산횟수
    while x != queue[(pointer+left)%(N-idx)]:
        left += 1

    # 오른쪽으로 탐색
    right = 0 # 3번 연산횟수
    while x != queue[(pointer-right)%(N-idx)]:
        right += 1

    # 더 적은 탐색횟수로 이동
    if left > right:
        res += right
        pointer = (pointer-right)%(N-idx) #포인터 갱신
        queue.pop(pointer) #항목 꺼내기

    else:
        res += left
        pointer = (pointer+left)%(N-idx) #포인터 갱신
        queue.pop(pointer) #항목 꺼내기
print(res)

 매번 큐를 앞뒤로 움직이는 대신, 꺼낼 첫 번째 항목 위치를 가리키는 포인터를 움직입니다.

 포인터 위치에서 꺼낼 항목이 왼쪽과 오른쪽 중 어느 쪽에 더 가까운지 판별하고, 가까운 쪽으로 연산을 해서 빼냅니다. 최소의 연산횟수로 꺼내야 하므로, 2번과 3번이 번갈아 쓰이는 경우는 없습니다.

 

 

 # 왼쪽으로 탐색
    left = 0 # 2번 연산횟수
    while x != queue[(pointer+left)%(N-idx)]:
        left += 1

 왼쪽으로 이동하므로 pointer에서 left를 더해주며, 끝에 도달하면 다시 맨 앞으로 넘어가도록 항목 개수(N-idx)로 나머지 연산해줍니다.

 

 # 오른쪽으로 탐색
    right = 0 # 3번 연산횟수
    while x != queue[(pointer-right)%(N-idx)]:
        right += 1

 반대로 오른쪽으로 탐색할 때에는 right만큼 빼줍니다. 이 때도 음수 인덱스가 되면 안되므로 항목 개수(N-idx)로 나머지 연산해줍니다.

 예를 들어 -1 % 5는 4이므로 자연스럽게 끝으로 넘어갑니다.