1158번 /요세푸스 문제 / 파이썬/ 큐

Queue

import collections import deque
queue = deque()

 

 

큐 구현을 위해 deque 라이브러리 사용!

- 파이썬에서 리스트로 구현 가능하지만 시간복잡도가 높아서 비효율적

- 스택과 큐 라이브러리 장점 합침

 

queue.append() :  삽입 시 

queue.popleft() : 삭제시

queue.reverse() : 역순으로 

 

 

 

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

 

 

 

 

 

# 1~n번까지 n명의 사람
# 제거되는 순서가 요세푸스 순열

from collections import deque

queue = deque()
result = []

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

# 1~n번 사람 큐 생성
for i in range(1,n+1):
    queue.append(i)

# print(queue)


while queue:
    for _ in range(k-1):
        # 왼쪽 첫번째 수 제거하고 큐에 오른쪽에 추가, k-1번 실행
        queue.append(queue.popleft())

#  왼쪽 첫번 째 숫자 queue에서 제거 후 result배열에 추가
    result.append(queue.popleft())

print(str(result).replace('[','<').replace(']','>'))

 

< > 로 출력할 때 replace 함수 사용하기

 

 

참고

 

https://velog.io/@thguss/백준-1158.-요세푸스-with.-Python-큐-문제에서-deque는-필수-별꼬리-땅땅

백준 1158. 요세푸스 (with. Python) - 큐 문제에서 deque()는 필수 별꼬리 땅땅