BOJ_12873 : 기념품

👉 문제링크

12873번: 기념품

---

---

🔸 문제 분석 🔸

• 1~N원소 중 1, 2, 3...의 3제곱 번째 원소를 제거하며 1개가 남을때까지 반복하는 문제이다.

🔸 코드 🔸

from collections import deque
import math

N = int(input())
t = 0
member = deque(range(1,N+1))

while len(member) != 1:
    t += 1
    member.rotate(-((int(math.pow(t,3))%len(member))-1))
    member.popleft()
print(member.pop())

🔸 코드 해석 🔸

• 데크 자료구조를 이용해 rotate()와 popleft()를 사용했다.
  • 문제에서 백준이의 이동을 큐의 rotate()로 구현했다.
  • 반복수를 줄이기 위해 전체 데크 크기로 나누어 주었다.
  • rotate()방향을 popleft() -> append() 방향으로 하기위해 -1를 곱해 음수로 만든다.
    (0은 정지, 양수는 pop() 방향)

---

🔸 end 🔸

• 원소의 삭제를 끝 부분에서 진행하고, 백준이의 이동을 편하게 구현하기 위해 데크를 썼는데 알맞게 사용한 것 같다.
• 리스트로 구현해서 pop(인덱스)로 지워줄 수도 있겠지만 큐라고 할 수 없을것이다.