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

https://www.acmicpc.net/problem/11866

11866번: 요세푸스 문제 0

 

 

처음 생각한 풀이 

queue를 돌려서 넘어가서 popleft하기.. 

import sys 

n,k = map(int, sys.stdin.readline().split()) 

from collections import deque 
queue = deque()

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

list = []
while len(queue) > 0:
    for i in range(2):
        queue.append(queue.popleft())
    list.append(str(queue.popleft()))

print("<", ", ".join(list), ">", sep="")

근데 이렇게 하면 시간복잡도가 너무 커서 안됨

 

그래서 다른 분들꺼를 참고해보니 리스트로 큐를 구현해서 인덱싱을 사용해야 한다는걸 알게됨 

아래는 수정한 코드

import sys 

n,k = map(int, sys.stdin.readline().split()) 

queue = list(range(1,n+1))
index = 0
list = []

while len(queue) > 0:
    index += (k-1) 
    if index >= len(queue):
        index = index % len(queue)
    list.append(str(queue.pop(index)))

print("<", ", ".join(list), ">",sep="")

 

 

한줄평 

시간복잡도 고려랑 출력 형식 맞춰주는게 은근 빡셋음. join 함수랑 sep 복습하기!