[Python]백준 #11866 요세푸스 문제 0

✔️알고리즘

• 구현
• 자료구조
• 큐

✔️접근방법

1. 덱을 사용해 반복할때마다 3번째 요소가 가장 앞에 오도록 rotation해준 후, pop 해준다.

from collections import deque

N, K = map(int, input().split())

deq = deque()      # deque객체 생성
for i in range(N): # deque에 1~N까지 삽입
    deq.append(i+1)

for i in range(N):
    deq.rotate(-(K-1)) #3번째 요소가 가장 앞에 오도록 rotation
    if (i == 0):
        print('<',end="")
    print(deq.popleft(),end="")
    if (i == N-1):
        print('>')
        break
    print(', ',end="")

 

✔️배운점/어려운점

1. 부끄럽지만 여태 원형큐 구현 방법을 습득하지 못해 다시 공부했다.

<원형큐 규칙>

   1) front == rear 면 empty

   2) (rear+1) % (큐 크기) == front  

   3) 원형큐의 한 공간은 빈다

* '큐' 자료구조 공부 

 

2. 파이썬 데크(deque) 자료구조를 공부했다.

<덱(deque)>

   1) 앞, 뒤 양방향으로 요소를 추가하거나 삭제할 수 있다.

   2) 일반적인 리스트는 연산에 O(n)가 소모되지만 덱의 경우 O(1)의 시간이 소모된다.

   3) 덱 메소드에는 append(item), appendleft(item), pop(), popleft(), remove(item),

                               rotate(num)(num이 음수면 왼쪽으로 이동, 양수면 오른쪽으로 이동),

                               extend(array), extendleft(array) (주어진 배열을 순환하면서 덱에 요소 추가)