[파이썬] 1158번: 요세푸스 문제

1158번: 요세푸스 문제 (acmicpc.net)

1158번: 요세푸스 문제

리스트로 푸니 시간초과가 발생하여 deque 라이브러리를 이용했다.

 

[구조]
n과 k 입력받기
덱에 1부터 n까지 넣기
k-1번째 원소까지는 팝하자마자 다시 덱에 넣기
k번째 원소는 팝하여 josephus 순열 리스트에 저장
출력 형식에 맞도록 코드 작성

 

나의 풀이

from collections import deque
import sys

n , k = map(int, sys.stdin.readline().split())
D = deque()
josephus = []

# n까지 큐에 넣기
for i in range(1, n + 1):
    D.append(i)

# k번째 원소는 팝하여 josephus 리스트에 삽입
while len(D) > 0:
    for j in range(1, k):
        D.append(D.popleft())
    josephus.append(str(D.popleft()))

# 출력 양식에 맞게 코드 작성
print("<{}>".format(', '.join(josephus)))

 

 

시간초과가 나지 않게 리스트로 풀 수 있는지 알고 싶어 구글링해보니 나머지를 이용하는 방법이 있었다.

백준에서 이 문제는 큐로 분류되어 있어 참고만 하면 좋을 것 같다.

참고 링크: [백준][Python] 1158번 요세푸스 문제 (tistory.com)