백준 11866번 요세푸스 문제 0

요세푸스 문제는 원으로 둘러 앉은 N명이 주어졌을 때, K번째 사람을 제거하는 문제다.

 

자료 구조 중 큐(Queue)를 사용해 풀이하였다.

 

다음과 같은 형태의 큐에서

[1, 2, 3, 4, 5, 6, 7]

 

가장 먼저 입력된 요소를꺼내 큐에 다시 넣어주는 과정(회전)을 무한히 반복한다면 

[1, 2, 3, 4, 5, 6, 7]
[2, 3, 4, 5, 6, 7, 1] <- 큐에서 1을 꺼내 다시 넣어준다.
[3, 4, 5, 6, 7, 1, 2] <- 큐에서 2를 꺼내 다시 넣어준다.
[4, 5, 6, 7, 1, 2, 3]               .
[5, 6, 7, 1, 2, 3, 4]               .
[6, 7, 1, 2, 3, 4, 5]               .
[7, 1, 2, 3, 4, 5, 6]               .
[1, 2, 3, 4, 5, 6, 7] <- 시작했던 큐의 형태로 돌아온다.

 

문제와 같이 N명이 원을 그리며 앉은듯한 형태를 만들 수 있다.

 

이제 큐(원)에 포함된 K번째 요소(사람)를 꺼내기 위해서는 큐를 K-1번 회전시켜야 한다.

for (int i = 0; i < k-1; i++) {
	int temp = queue.poll(); // 가장 앞의 요소를 꺼내고
	queue.offer(temp); // 큐에 다시 넣는다
}

num = queue.poll(); // K번째 요소가 첫번째로 이동했으므로 꺼낸다.

 

위 방식을 응용하여 작성한 코드는 다음과 같다.

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

public class Main {
    public static void main(String[] args) {

        LinkedList<Integer> q = new LinkedList<>();

        Scanner in = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        sb.append("<");

        int N = in.nextInt(); // 큐 사이즈
        int K = in.nextInt(); // 회전 수

        // 큐 생성
        for (int i = 1; i <= N; i++) {
            q.offer(i);
        }

        for (int n = 0; n < N; n++) {

            if (q.size() == 1) {
                sb.append(q.poll()).append(">");
                break;
            }

            for (int i = 0; i < K - 1; i++) {
                q.offerLast(q.pollFirst());
            }
            sb.append(q.pollFirst()).append(", ");
        }
        System.out.println(sb);
    }
}