큐-몸풀기 문제

문제 15 요세푸스 문제

N명의 사람이 원 형태로 서있고, 각각 1~N까지 번호표를 갖고 있음
임의의 숫자 K가 주어졌을 때 1번 번호표를 가진 사람을 기준으로 K번째 사람을 없앰

시간복잡도 : O(N*K)

from collections import deque

def solution(N,K):
	queue=deque(range(1,N+1))
    while len(queue)>1:
    	for _ in range(K-1):
    		queue.append(queue.popleft())
        queue.popleft()
return queue[0]
print(solution(5,2)
    

시간복잡도는 K-1번 팝하고 푸시하는 걸 N번 반복하므로 O(N*K)

cf ) range는 리스트가 아니지만 리스트처럼 동작할 수 있는 이터러블 객체
deque는 이터러블을 처리할 수 있으므로 굳이 list(range(...))로 변환하지 않아도 된다 !

popleft는 인수 (0) 추가할 필요 없음, pop(0) 그리고 popleft()

+다른 풀이 방법은 백준 #1158 해설에