백준 1158번 - 요세푸스 문제

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

1158번: 요세푸스 문제

 

 

 

 

 

 

처음에 어떻게 풀어야 하나 고민을 했다. Node 클래스를 직접 만들어서 문제에 맞게 큐로 순환이 되도록 add와 pop, remove 등의 메소드를 직접 만들어야 하나 생각했었다. 하지만 그렇게 하기에는 번거롭고 더 복잡해 보인다.

 

그냥 큐로 구현을 하는데, K번째 앞까지는 뽑아서 다시 뒤로 삽입하고 K번째 원소는 뽑아버리고를 반복하면 된다!

 

 

 

 

 

코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int K = sc.nextInt();

		Queue<Integer> queue = new LinkedList<>();
		
		for(int i = 1; i <= N; i++) {
			queue.add(i);
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append("<");
		
		while(queue.size() > 0) {
			for(int i = 0; i < K - 1; i++)  {
				int p = queue.poll(); //앞의 원소 뽑아서
				queue.add(p); //뒤로 다시 삽입
			}
			
			if(queue.size() != 1) { //K번째 제거
				sb.append(queue.poll() + ", ");
			}else {
				sb.append(queue.poll());
			}
		}
		
		sb.append(">");
		
		System.out.println(sb);
	}

}

 

 

 

 

 

 

결과