[ 백준 11866번 문제 ] 요세푸스 문제 0

이번 글에서 백준 11866번 문제를 통해 요세푸스 순열을 활용,
이를 통해 원형 큐와 결합하여 사용해보자.

문제 핵심

• N : 사람 수
• K : 건너뛸 수
• ( 1 <= K <= N <= 1,000 )

풀이 과정

다음 문제는 요세푸스를 순열을 통해 한 사람씩 제거해 나가는 문제이다.

다음 글을 통해 개념을 참고하면 좋을 것 같다. 비교적 간단하다.

플라비우스 요세푸스 순열

 

1. 반복

해당 문제는 K의 배수마다 값을 꺼내오면 된다.

때문에 이전 값들은 모두 다시 큐의 뒤에 넣어주고 그 과정을 마지막 한 사람이 남을 때까지 반복해준다. 

        while(1 < queue.size()) {
            count++;
            if(count % K == 0){
                stringBuilder.append(queue.remove() + ", ");
                continue;
            }
            queue.add(queue.remove());
        }

 

2. 출력

백준의 문제 출력 조건에 따라 마지막 값은 기호와 함께 처리해 준다.

        stringBuilder.append(queue.remove() + ">");
        System.out.println(stringBuilder);

이번 문제는 큐의 개념과 요세푸스 순열을 이해하고 있다면, 
결합하여 아주 쉽게 풀 수 있는 문제이다.
요세푸스 문제는 재귀로도 풀 수 있는 만큼 한 번 시도해보는 것도 좋다.

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Queue<Integer> queue = new LinkedList<Integer>();
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("<");
        int N = Integer.parseInt(stringTokenizer.nextToken());
        int K = Integer.parseInt(stringTokenizer.nextToken());


        for(int i = 0; i < N; i++) {
            queue.add(i + 1);
        }
        int count = 0;

        while(1 < queue.size()) {
            count++;
            if(count % K == 0){
                stringBuilder.append(queue.remove() + ", ");
                continue;
            }
            queue.add(queue.remove());
        }

        stringBuilder.append(queue.remove() + ">");
        System.out.println(stringBuilder);

    }
}