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

문제

11866번: 요세푸스 문제 0

 

---

풀이

from collections import deque

queue = deque()
josephus = []

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

for i in range(1, n + 1):
    queue.append(i)

while queue:
    for i in range(k - 1):
        queue.append(queue.popleft())
    josephus.append(queue.popleft())

print("<", end="")
print(", ".join(map(str, josephus)), end="")
print(">")

 

range(k - 1) 부분을 이해하는데 좀 걸렸다. 손으로 하나 하나 넣어보다보면 이해가 간다.

k번째가 되면 queue에서 빼 josephus에 넣어주고, k번째가 될 때까지 앞에서 빼서 다시 뒤로 넣고 있으면 된다.

 

- 출력방식 주의

 

- deque가 자주 등장하는데 사용법을 제대로 숙지하자.

 

collections.deque

• appendleft(x): 데크 왼쪽에 x 추가
• popleft(x): 데크 왼쪽에서 요소를 제거
• rotate(x): x만큼 오른쪽으로 회전(양수), 왼쪽으로 회전(음수)

 

• deque는 list보다 속도가 빠르다. pop(0)와 같은 메서드를 수행할 때 리스트라면 O(N) 연산을 수행하지만, deque는 O(1) 연산을 수행하기 때문이다.
• 스레드 환경에서 안전하다.

 

빅오 표기법 Tip!

• O(1) - 입력의 크기와 상관 없이 항상 같은 시간이 걸리는 알고리즘이다. 리스트나 딕셔너리의 데이터에 접근할 때 O(1)의 시간 복잡도를 갖는다.
• O(logN) - 문제를 해결하는데 필요한 단계들이 연산마다 줄어드는 알고리즘이다. 이진탐색, 힙 삽입/삭제 등이 O(logN)의 시간 복잡도를 갖는다.
• O(N) - 한번의 반복을 수행하고 완료되는 선형 탐사가 O(N)의 시간 복잡도를 갖는다.
• O(N^2) - 2중 반복을 돌게되는 알고리즘은 O(N^2)의 시간 복잡도를 갖는다.