BOJ

BOJ 1158 - 요세푸스 문제

yanJuicy 2024. 1. 28. 23:22
반응형

문제

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

 

1158번: 요세푸스 문제

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

www.acmicpc.net

 

 

 

풀이

큐를 이용해 문제를 해결할 수 있다.

큐에서 k - 1 번 데이터를 front에서 pop하고 rear에 넣어준다. 이것이 원을 이루면서 앉아있는 것과 같아진다.

그 다음 k 번째에 데이터를 pop한다.

이를 q가 빌 때까지 반복하고 pop한 숫자들을 차례대로 저장해 출력한다.

 

 

 

코드

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from collections import deque
 
def solution(n, k):
    answer = []
    q = deque(range(1, n + 1))
    while q:
        for _ in range(k - 1):
            q.append(q.popleft())
        answer.append(q.popleft())
    return answer            
 
n, k = map(int, input().split())
answer = solution(n, k)
 
print(str(answer).replace('[','<').replace(']','>'))
cs

 

반응형

'BOJ' 카테고리의 다른 글

백준 17472 - 다리 만들기 2  (1) 2023.03.06
백준 6416 - 트리인가?  (0) 2022.11.28
백준 1620 - 나는야 포켓몬 마스터 이다솜  (0) 2022.11.18
백준 2559 - 수열  (0) 2022.03.20
백준 2003 - 수들의 합 2  (0) 2022.03.17