baekjoon(1158-요세푸스 문제)_ python

1) 문제

 

2) 예시

3) 제출

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
queue = list(range(1, n+1))
res = "<"
i = 0
while len(queue)>1:
    i = (i + k - 1) % len(queue)
    res += str(queue.pop(i)) + ", "
print(res + str(queue.pop()) + ">")

4) 메모리/시간/코드길이

5) PLUS

(처음 시도했던 방법)

import sys
input = sys.stdin.readline

queue = []
n, k = map(int, input().split())
queue = [num for num in range(1, n + 1)]

res = "<"
while len(queue) > 1:
    for i in range(0, k-1):
        queue.append(queue.pop(0))
    res += str(queue.pop(0)) +", "

res += str(queue.pop()) + ">"
print(res)

=> k 만큼 pop과 append를 반복하고 k 반복문을 빠져나갈 때 res라는 문자열에 저장을 해주었다. 

결과적으로 시간 초과가 났다,,

 

어떻게 해야 할지 한참 고민하는 중에 circular queue로 풀면 된다는 것을 알게 되었다.

원형큐를 어떻게 구현해야 하는지 front를 정의하고 rear를 정의할지 새로운 함수를 만들어야 하는지 한참 고민했다.

https://youtu.be/DEXpIZpfqiQ

이 영상을 찾아보고 index를 전체 크기로 나눈 나머지 값으로 보면 쉽게 구현될 것이라는 생각을 하게 되었고

    i = (i + k - 1) % len(queue)​

이 코드를 작성하게 되었다.

 

queue = [num for num in range(1, n + 1)]
queue = list(range(1, n+1))

=> 리스트를 초기화할 때 첫 번째 줄로 선언했는데 for 문을 쓰지 않고 range로 간편하게 할 수 있는 방법도 있다.