1158번: 요세푸스 문제
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)
www.acmicpc.net
아이디어: #큐
큐를 이용해서 n까지의 수를 모두 넣은 후 앞에서부터 차례대로 제거하면서 제거한 수를 다시 큐에 집어넣는 형태로 반복한다.
파이썬에서 queue를 구현하는 방법
1. 리스트 - 비효율적임
2. Queue
# 내장 함수 queue를 사용하여 구현
import queue
q = queue.Queue()
q.put("a")
q.put("b")
q.put("c")
q.qsize() # 3
q.get() # 'a'
q.qsize() # 2
근데 queue를 이용해서 문제를 풀었더니 시간초과가 나왔다.. 질문을 보니 queue는 단일 스레드에서 사용하기엔 비효율적이라고 하더라.
#시간초과
import sys, queue
n, k = map(int, sys.stdin.readline().split())
q = queue.Queue()
ans = []
for i in range(1,n+1):
q.put(i)
index = 1
while (q.qsize()!=0):
for i in range(k-1):
q.put(q.get())
ans.append(q.get())
print("<", end="")
for i in range(n-1):
print("%d, "%ans[i], end="")
print("%d>"%ans[-1])
그래서 deque를 사용해보았다.
-> 파이썬 deque 사용법
코드:
#시간초과
import sys
from collections import deque
n, k = map(int, sys.stdin.readline().split())
q = deque()
ans = []
for i in range(1,n+1):
q.append(i)
while (len(q)!=0):
for i in range(k-1):
q.append(q.popleft())
ans.append(q.popleft())
#답 출력
print("<", end="")
for i in range(n-1):
print("%d, "%ans[i], end="")
print("%d>"%ans[-1])
'알고리즘💻 > 스택&큐&덱' 카테고리의 다른 글
BOJ 2504번: 괄호의 값 (0) | 2021.02.01 |
---|---|
BOJ 1021번: 회전하는 큐 (0) | 2021.02.01 |
BOJ 1966번: 프린터 큐 (0) | 2021.01.31 |
BOJ 4949번: 균형잡힌 세상 (0) | 2021.01.31 |
BOJ 1935번: 후위 표기식2 (0) | 2021.01.31 |