[백준] 1158 요세푸스 문제 - 큐 + 자료구조 JAVA

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

1158번: 요세푸스 문제

코드설명

큐 자료구조 문제입니다.

 

혹은 LinkedList를 사용하여 해결할 수 있습니다. (next, prev 위치를 저장)

 

문제로직입니다. 만약 K=3 이라고 가정합니다.

1. 3번째 Queue 값을 구하기 위해서는 1번쨰 2번째 Queue값을 넘기고 3번쨰 Queue값을 사용해야합니다. 

2. 이때 1번쨰 2번째 Queue값을 뺀뒤에 다시 q.offer( q.poll() ) 로 넣습니다. 뺴는 동시에 다시 뒤로 넣어서 이후에 다시 사용할 수 있도록 합니다.

3. 마지막의 경우는 q.size() == 1 이라면 중단시키고, ', >' 처리를합니다.

 

코드

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

public class Main {
	public static int N, K;
	public static Queue<Integer> q = new LinkedList<>();
	public static StringBuilder sb = new StringBuilder();
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	K = Integer.parseInt(st.nextToken());
    	
    	for(int i=1;i<=N;i++) { //1부터 N까지 값을 q에 삽입
    		q.offer(i);
    	}
    	
    	sb.append("<");
    	
    	
    	// Queue의 Size가 1이 될때까지 반복 (1개 남으면 종료시키고, '숫자>' 출력시키기 위함입니다.
    	while(q.size() != 1) {
    		// K - 1 번째까지 처음에 있던 값을 맨뒤로 보냅니다.
    		for(int i=0;i<K-1;i++) {
    			q.offer(q.poll());
    		}
    		int kFind = q.poll();
    		sb.append(kFind+", ");
    	}
    	int kFind = q.poll();
    	sb.append(kFind+">");
    	System.out.println(sb.toString());
    }
    
    
    
}