[BOJ] 1021. 회전하는 큐 (Python/자료구조/Silver 3)

 

---

[문제 링크] 👉https://www.acmicpc.net/problem/1021

---

풀이

💡 카드의 절반 기준으로 문제를 푼다.

 

 

빼내려는 카드가 중간 보다 왼쪽에 있을 때 2번 연산을 한다.

n_deq.rotate(-1)

• 큐를 왼쪽으로 1만큼 회전

 

반대로 빼내려는 카드가 중간 보다 오른쪽에 있을 때 3번 연산을 한다.

 n_deq.rotate(1)

• 큐를 오른쪽으로 1만큼 회전

 

Solution

from collections import deque

n, m = map(int, input().split())
pop_num = list(map(int, input().split()))
n_deq = deque()
for i in range(1, n + 1):
    n_deq.append(i)
result = 0
for i in pop_num:
    while n_deq[0] != i:
        if n_deq.index(i) == 0:  # 0번 인덱스가 빼내려는 수랑 같을 때까지
            n_deq.popleft()
        elif n_deq.index(i) <= len(n_deq) // 2:  # 중간보다 이하일 때 왼쪽으로
            n_deq.rotate(-1)  # 1만큼 왼쪽으로 회전(반시계)
            result += 1
        else:
            n_deq.rotate(1)  # 1만큼 오른쪽으로 회전(시계)
            result += 1
print(result)

 

위 코드의 개선 사항

• while n_deq[0] != i 조건 사용
  • 덱의 첫 번째 요소가 i가 될 때까지 회전하여 덱을 정렬하지 않고 필요한 회전만 수행
• 불필요한 index() 호출 제거
  • 덱을 직접 확인하여 회전 방향을 결정하기 때문에 n_deq.index(i)의 반복 호출을 피할 수 있다.

 

최적화된 코드

from collections import deque

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

# 1부터 n까지의 숫자를 덱에 추가
n_deq = deque(range(1, n + 1))
result = 0

for i in pop_num:
    while n_deq[0] != i:  # 빼낼 숫자가 첫 번째 위치에 오도록 회전
        if n_deq.index(i) <= len(n_deq) // 2:  # 중간보다 왼쪽에 가까우면 왼쪽 회전
            n_deq.rotate(-1)
        else:  # 오른쪽에 가까우면 오른쪽 회전
            n_deq.rotate(1)
        result += 1
    n_deq.popleft()  # 첫 번째 위치에 있으면 뽑아내기

print(result)

 

 

👩‍💻 회고

제출 전에 테스트 케이스로 검증을 해보는데 옳은 결과가 제대로 나오지 않았었다. 최솟값으로 출력이 안 되고 있었는데 그 이유는 다음과 같았다. 카드를 빼는 연산이 있기 때문에 카드의 수가 줄어들어 카드를 절반으로 나눌 때 현재 카드의 수만큼 나눠야 한다. 그러나 나는 입력받은 카드 수인 n 을 절반으로 나누고 있어서 값이 제대로 나오지 않고 있었던 것이었다.

다행히도 테스트 케이스가 여러개가 있어서 제출 전에 수정하고 원트에 성공할 수 있었지만, 한 개의 케이스만 있었다면 아마 갈피를 못 잡았을 것 같다. 역시 테스트 케이스를 만들어보고 여러번 검증해보는 과정이 중요한 것 같다.

---