백준20301

문제

요세푸스 문제는 다음과 같다.

 $1$번 사람 오른쪽에는 $2$번 사람이 앉아 있고, $2$번 사람 오른쪽에는 $3$번 사람이 앉아 있고, 계속하여 같은 방식으로 $N$명의 사람들이 원을 이루며 앉아 있다. $N$번 사람 오른쪽에는 $1$번 사람이 앉아 있다. 이제 $K$($\leq N$)번 사람을 우선 제거하고, 이후 직전 제거된 사람의 오른쪽의 $K$번째 사람을 계속 제거해 나간다. 모든 사람이 제거되었을 때, 제거된 사람의 순서는 어떻게 될까?

이 문제의 답을 ($\boldsymbol{N}$, $\boldsymbol{K}$)–요세푸스 순열이라고 하며, ($7$, $3$)–요세푸스 순열은 $\left<3, 6, 2, 7, 5, 1, 4\right>$가 된다.

하지만 한 방향으로만 계속 돌아가는 건 너무 지루하다. 따라서 요세푸스 문제에 재미를 더하기 위해 $M$명의 사람이 제거될 때마다 원을 돌리는 방향을 계속해서 바꾸려고 한다. 이렇게 정의된 새로운 문제의 답을 ($\boldsymbol{N}$, $\boldsymbol{K}$, $\boldsymbol{M}$)–반전 요세푸스 순열이라고 하며, ($7$, $3$, $4$)–반전 요세푸스 순열은 $\left<3, 6, 2, 7, \mathbf{1}, \mathbf{5}, \mathbf{4}\right>$가 된다.

 $N$, $K$, $M$이 주어질 때, ($N$, $K$, $M$)–반전 요세푸스 순열을 계산해 보자.

입력

첫째 줄에 정수 $N$, $K$, $M$이 주어진다. ($1 \leq N \leq 5\ 000$, $1 \leq K, M \leq N$)

출력

($N$, $K$, $M$)–반전 요세푸스 순열을 이루는 수들을 한 줄에 하나씩 순서대로 출력한다.

예제 입력

7 3 4

예제 입력

3
6
2
7
1
5
4

시도

• 원형 큐로 생각하고 문제를 풀었다.
• 제거된 사람들의 자리가 그대로 유지되는 거라고 생각하고 풀었으나, 제거 된 경우 자리 역시 함께 제거 되는 것이었다.
• 원형 큐의 경우 인덱스 마지막 번호에 다다르면 다시 인덱스를 0으로 초기화를 시켜주어야 한다.
• 그런데 중간의 원소들이 제거 될 경우, 제거된 원소 이후에 있는 원소들의 인덱스가 변하기 때문에 다시 인덱스를 초기화시키고 제거할 원소를 찾는 부분을 구현하는데 어려움이 있었다.

풀이

• 양방향으로 추가, 제거가 가능한 Deque를 이용한다

입력이 아래와 같다고 가정하자. 이 경우에 3번째에 있는 원소를 먼저 제거하고, 이후에 오른쪽 3개씩 떨어져 있는 자리에 있는 원소를 제거한다. 그리고 이 과정이 4번 반복 되면 방향을 반대로 바꾸어 왼쪽에 3개씩 떨어져 있는 원소를 찾아 제거한다.

7 3 4

이 경우 큐에는 다음과 같이 값이 들어간다

1 2 3 4 5 6 7

그리고 우리가 먼저 제거해야 할 원소는 3번째 자리에 있는 3이다. 그렇다면 Deque를 이용해 제거할 대상이 아닌 원소들은 poll한 뒤, poll한 위치의 반대편으로 다시 offer 해 주어 다음 차례에 다시 탐색하도록 만든다.

어떤 것을 제거 할 것인지는 count라는 변수를 이용한다. 한번 poll을 진행할 때마다 1씩 증가해주고, count가 K와 같을 경우 해당 원소를 제거하고, 다시 0으로 초기화 시켜준다.

이렇게 하면 큐 사이즈가 변함에 따라 인덱스가 변하고, 끝 자리의 인덱스를 넘어가서 다시 인덱스를 찾아줘야 하는 문제를 고려하지 않아도 되게 된다.

또한 M 번 제거가 이루어질 때마다 탐색 방향을 바꿔주기 위해서, count=0이 이루어질 때 directionCount의 값을 1씩 증가 시켜주고, 이 값이 M과 같아질때마다 탐색 방향을 전환시켜준다.

// count = 1
// directionCount = 0
2 3 4 5 6 7 1
// count = 2

// count = 2
// directionCount = 0
3 4 5 6 7 1 2
// count = 3

제거 대상이 아닌 1, 2를 맨 뒤로 추가한 뒤 제거할 대상인 3이 등장하면 제거하고 출력한다. 이때 이 3은 다시 추가하지 않는다. 이후 큐의 모습은 아래와 같다.

// count = 0
// directionCount = 1
4 5 6 7 1 2
// count = 1

계속 해서 보자 그 다음 제거 대상은 6이다. 아래와 같이 제거 대상이 아닌 경우 poll 의 반대 방향에 원소를 추가 해주고

// count = 2
// directionCount = 1
6 7 1 2 4 5
// count = 3

해당 원소를 제거한 뒤 출력한다.

// count = 0
// directionCount = 2
7 1 2 4 5
// count = 1

그 다음 과정을 쭉 보자

// count = 2
// directionCount = 2
2 4 5 7 1
// count = 3

// count = 0 
// directionCount = 3
4 5 7 1
// count = 1

// count = 2
// directionCount = 3
7 1 4 5
// count = 3

// count = 0
// directionCount = 4
1 4 5
// count = 1
// directionCount = 0

M에 해당하는 4번의 제거가 이루어졌으므로, 방향을 바꿔준다. 이 때부터 pollFirst가 아닌 pollLast로 뒤에서 부터 탐색을 시작하고, 제거 대상이 아닌 경우 추가는 offerFirst를 이용해 앞에 추가를 해준다.

다음은 이를 코드로 작성한 것이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.valueOf(st.nextToken());
        int K = Integer.valueOf(st.nextToken());
        int M = Integer.valueOf(st.nextToken());
        Deque<Integer> q = new ArrayDeque<Integer>();

        for(Integer i=1; i<=N; i++)
            q.add(i);

        int count = 0;
        int directionCount = 0;
        boolean isLeftToRight = true;

        while (!q.isEmpty()) {
            int number;
            if (isLeftToRight) {
                number = q.pollFirst();
            } else {
                number = q.![](https://velog.velcdn.com/images/saint6839/post/7d234418-d819-4998-a919-7f0c8a91f3ca/image.png)
pollLast();
            }

            count += 1;
            if (count == K) {
                count = 0;
                directionCount += 1;
                sb.append(number)
                  .append("\n");
            } else {
                if(isLeftToRight) {
                    q.addLast(number);
                } else {
                    q.addFirst(number);
                }
            }

            if (directionCount == M) {
                directionCount = 0;
                isLeftToRight = !isLeftToRight;
            }
        }
        System.out.println(sb);
        br.close();
    }
}