[BOJ] 11866번: 요세푸스 문제

🔗 https://www.acmicpc.net/problem/11866

 

이 문제는 N과 K를 입력 받았을 때, 1부터 N까지의 원 안에서 K번째 수를 제거하고 그 수로부터 K번째 수를 또 제거하는 과정을 원 순열이 모두 비워질 때까지 반복한다.

 

예를 들어 N과 K로 각각 7과 3를 입력했다면,

 

1,2,3,4,5,6,7 (K=3, 세번째 수 3 제거)

1,2,4,5,6,7 (앞선 3에서부터 세번째 수인 6 제거)

1,2,4,5,7 (6에서부터 세번째 수인 2 제거, 순열이 원으로 이뤄져있음)

같은 과정 반복 시 7, 5, 1, 4 제거

 

따라서 결과 순열은 3, 6, 2, 7, 5, 1, 4가 된다.

 

이런 논리를 코드로 구현하면 된다.

 

---

시도 1) 직접 배열 이용하기

import java.util.Scanner;

public class BOJ_11866 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N, K;
        N = sc.nextInt();
        K = sc.nextInt();
        int[] arr = new int[1001];
        int[] result = new int [N];

        for (int i = 1; i <= N; i++) {
            arr[i] = i;
        }

        int idx = 1;

        for (int j = 0; j < N; j++) {
            for (int i = 0; i < K; idx++) {
                if (idx > N){
                    idx %= N;
                }

                if (arr[idx] == 0){
                    continue;
                }

                if (i == K-1){
                    result[j] = arr[idx];
                    arr[idx] = 0;
                }

                i++;
            }
        }

        System.out.print("<");
        for (int i = 0; i < N-1; i++) {
            System.out.print(result[i]+", ");
        }

        System.out.println(result[N-1]+">");
    }
}

 

처음 접근은 위와 같다. arr 배열에 1부터 N까지의 숫자를 넣고, K번째 숫자를 제거하는 로직은 그 숫자를 0으로 바꿔주는 것으로 한다.

 

K번째 숫자에 다다르기까지 숫자 하나 하나(arr 배열의 idx번째)를 검토하는데, 만약 검토되는 숫자가 0으로 바꿔져있다면 즉, 순열에서 빠진 숫자라면 건너뛴다. 건너뛴다는 것은 검토 횟수(안쪽 for문의 인덱스 i)를 증가시켜주지 않고 다음 숫자(idx++)로 바로 넘어가는(continue) 것이다. 그렇게 하여 검토 횟수가 K번째가 되면, 즉, K번째 숫자에 도달하면 result 배열에 수를 넣어준다.

이 과정을 이어서 총 N번 반복한다.

 

정답..

백준에 제출하였을 때 정답이긴 했지만, 내가 생각해도 로직이 너무 복잡한 것 같았다.

사실 처음에 원순열이니까 원형 큐를 써볼까 했지만 'K번째를 어떻게 빼지? 앞에서만 빼고 뒤로만 넣어야하는데.. '라는 생각을 하며 막혔었다. 하지만 좀 더 곰곰이 생각해보면 해결될 수 있는 문제였다...!

 

시도 2) 직접 배열 이용하기

import java.util.*;

public class BOJ_11866_2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N, K;
        N = sc.nextInt();
        K = sc.nextInt();

        Queue<Integer> queue = new LinkedList<>();

        // 요소 넣기
        for (int i = 1; i <= N; i++) {
            queue.add(i);
        }

        int[] result = new int[N];

        for (int i = 0; i < N; i++) {
            // K번 만큼 poll & add
            for (int j = 0; j < K-1; j++) {
                queue.add(queue.poll());
            }
            result[i] = queue.poll();
        }

        System.out.print("<");
        for (int i = 0; i < N; i++) {
            if (i == N-1)
                System.out.print(result[i]+">");

            else System.out.print(result[i]+", ");
        }
    }
}

 

큐를 이용했을 때의 방법이다.

 

예를 들어 함께 설명해보자면,

1, 2, 3, 4, 5, 6, 7 (K=3, 세번째 수 3 제거)

여기서 3을 제거할 때, 앞의 1, 2도 제거(poll)한다. 동시에, 1, 2는 계속 리스트에 있어야하므로 제일 뒤로 넣어주는 것도 해준다(add).

 

즉 이렇게 되는 것이다.

3, 4, 5, 6, 7, 1, 2 (3 제거 & 1, 2를 제거 + 뒤로 add)

 

이 과정을 총 N번 반복 해주면 된다.

성공..!

 

---

이번 문제에서는 큐에 대한 이해가 조금 부족했던 것 같다. 특히나 처음에는 자바의 큐 클래스 대신, 직접 배열로 큐 기능을 구현하려 해서 더 막혔다. 하지만 큐는 FIFO(선입선출) 논리 아래에서, 앞에서 요소를 빼주고 뒤에서 요소를 넣어주면 되는 자료구조 형태니까, 여전히 특정 요소를 남기고 싶다면 앞에서 뺐어도 그대로 뒤로 넣어주기만 하면 되는 것이었다...!

생각보다 간단한 문제였는데 떠올리지 못했던 나를 반성하며.. 글을 마쳐본다.