[백준] 1158: 요세푸스 문제

 

 

 

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.EmptyStackException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	
	// 요세푸스 문제 큐를 사용해서 다시 풀어보기

	public static void main(String[] args) throws IOException, NullPointerException{
		// StringBuilder를 사용하여 결과를 한 번에 출력하기 위한 객체 생성
        StringBuilder sb = new StringBuilder();

        // BufferedReader를 사용하여 입력을 받기 위한 객체 생성
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 저장할 큐 생성
        Queue<Integer> queue = new LinkedList<Integer>();
       	
       	StringTokenizer st = new StringTokenizer(br.readLine(), " ");
       	
       	int N = Integer.parseInt(st.nextToken());
       	
       	int K = Integer.parseInt(st.nextToken());
       	
       	// 1부터 N까지 큐에 삽입
       	for(int i = 1; i <= N; i++) {
       		queue.offer(i);
       	}
       	
       	sb.append('<');
       	
       	// 큐에 숫자가 하나만 남을 때까지 반복
       	while(queue.size() > 1) {
       		
       		if(queue.isEmpty()) {
       			break;
       		}
       		
       		for(int i = 0; i < K-1; i++) {
       			// 맨 앞 요소를 맨 뒤로 삽입
       			queue.offer(queue.poll());
       		}
       		
       		// K번째 요소 제거 및 sb에 추가
       		sb.append(queue.poll()).append(", ");
       		
       		
       		
       	}
       	
       	// 마지막 숫자 poll() & sb에 추가
       	sb.append(queue.poll()).append('>');
       	System.out.println(sb);
       	
	}
	

  

}

 

입력으로 N과 K를 받고, 1부터 N까지의 수를 갖는 큐를 만들었다.

그 후, 큐에 사람이 하나만 남을 때까지 반복하면서 K번째 사람을 제거하고 다시 큐에 넣는 작업을 수행한다.

큐에서 제거된 사람들은 결과를 출력하기 위한 StringBuilder에 저장되고 마지막에는 마지막으로 남은 사람을 큐에서 빼내어 결과(sb)에 추가한다.