Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

19. 큐, 덱

큐와 덱을 구현하고 사용해 봅시다.

Java / Python

3. 요세푸스 문제 0

11866번

큐를 이용해 제거 과정을 구현하는 문제

이번 문제는 요세푸스 문제입니다.
1부터 N까지 나열된 수에서 K 번째 수마다 차례대로 뽑아낸 수열을 출력하는 문제입니다.
K 번째 수가 되기 직전까지 맨 앞 원소를 K-1 번 (poll) 꺼내옵니다.
그 꺼낸 원소들을 맨 뒤로 (offer) 넣습니다.
K 번째로 뽑힌(poll) 원소를 출력합니다.

• Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
 
	public static void main(String[] args) throws IOException {
        
		Queue<Integer> queue = new LinkedList<>();	
        
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());		
		
		for(int i = 1; i <= N; i++) {
			queue.add(i);
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append('<');	// 출력형태 < ,,, > 

		while(queue.size() > 1) {
			
			for(int i = 0; i < K - 1; i++) {
				queue.offer(queue.poll());
			}			
			sb.append(queue.poll()).append(", ");
		} 
		sb.append(queue.poll()).append('>');	// 출력형태 < ,,, > 
		System.out.println(sb);
	}
}

• Python

import sys
from collections import deque
n, k = map(int, sys.stdin.readline().split())
queue = deque([])

for i in range(1, n + 1):
    queue.append(i)
    
print('<', end='')
while queue:
    for i in range(k - 1):
        queue.append(queue[0])
        queue.popleft()
    print(queue.popleft(), end='')
    if queue:
        print(', ', end='')
print('>')