백준 - 1021(회전하는 큐, 파이썬)

 

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

1021번: 회전하는 큐

문제 접근

• 큐를 최소한으로 회전시키며 값을 추출하는 문제
• 다행히 파이썬에는 큐를 회전시키는 rotate 함수가 있어서 편하게 구현
• 어떤 기준에 따라 오른쪽, 왼쪽으로 회전시킬지만 정해주면 될듯

 

처음에는 구하려는 값이 오른쪽 끝과 가까운지 왼쪽 끝과 가까운지를 판단해 큐를 회전시키려 했다.

from collections import deque


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

numbers = list(map(int, input().split()))

cnt = 0
q = deque()
for i in range(1, n+1):
    q.append(i)

while True:
    if len(numbers) == 0:
        break
    if q[0] == numbers[0]:
        numbers.pop(0)
        q.popleft()
        continue

    # 오른쪽과 더 가까우면 오른쪽 회전
    if abs(q[-1] - numbers[0]) > abs(q[0] - numbers[0]):
        q.rotate(-1)
        cnt += 1

    elif abs(q[-1] - numbers[0]) < abs(q[0] - numbers[0]):
        q.rotate(1)
   
        cnt += 1

print(cnt)

하지만 위처럼 작성했더니 while문이 종료되지 않거나 정답과 다른 값만 추출되었다...(왜지?)

 

 

원인을 파악하다가 그냥 조건을 바꾸기로 했다.

찾고자 하는 값을 오른쪽 끝, 왼쪽 끝과 비교하는 것이 아닌 중간을 기준으로 왼쪽에 있는지 오른쪽에 있는지를 파악해 돌리는 것으로 했다.

 

정답 코드

from collections import deque


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

numbers = list(map(int, input().split()))

cnt = 0
q = deque()
for i in range(1, n+1):
    q.append(i)

while True:
    if len(numbers) == 0:
        break
    if q[0] == numbers[0]:
        numbers.pop(0)
        q.popleft()
        continue

    # 오른쪽과 더 가까우면 오른쪽 회전
    if q.index(numbers[0]) <= len(q) // 2:
        q.rotate(-1)
        cnt += 1

    else:
        q.rotate(1)
   
        cnt += 1
print(cnt)

웬만하면 처음 떠올린 아이디어로 풀고 싶었지만 너무 시간 낭비같고 더 쉬운 방법이 떠올라 조건을 바꿔줬다..