[큐]queue 정리_1(백준_11866_요세푸스 문제 0)

1. 간단 정의

 - 선입선출로 돌아가는 데이터 임시 저장 방식이다.

 - 큐에서 유용하게 사용하게 되는 collections 라이브러리도 함께 소개한다.

 

2. 문제

문제

3. 문제 해석

 - 핵심은 리스트를 k 전까지 돌려주고 k번째는 별도의 리스트로 넣어 리스트를 줄인다.

 

4. popleft함수 

 - deque를 import 하면 사용할 수 있고 가장 앞의 요소롤 pop할 수 있다.

 - 시간복잡도가 pop과 동일하다.(중요)

 

5. 코드

import sys
from collections import deque
input = sys.stdin.readline
#리스트의 개수(n), 건너 뛰는 범위(k)
n, k = map(int, input().split())

n_list = deque([])
for i in range(1, n+1):
    n_list.append(i)
# queue 데이터를 넣기 위한 빈 리스트
queue = []
while True:
    for _ in range(k-1): # 맨 앞에 요소를 뒤로 push하는데, k-1만큼 넘긴다.
        n_list.append(n_list.popleft())
    
    queue.append(n_list.popleft()) # k번째는 queue리스트로 넣는다.
    if len(n_list) == 0: # 리스트가 0이 되면 break
        break

# 답에서 제시한 모양대로 만들어준다.
rere = ', '.join(map(str,queue))
print(f"<{rere}>")