요세푸스 문제

1번부터 N번까지의 사람이 동그랗게 모여서 앉아있습니다. 1번부터 순서를 세어 K 번째 사람을 모임에서 제외시킵니다. 남은 N-1명에서 이번에 제외된 다음 사람부터 원을 따라 다시 순서를 세서 K번째 사람을 모임에서 제외하는 과정을 마지막 사람이 남을 때까지 반복합니다. 이때 마지막으로 남는 사람의 번호를 구하는 프로그램을 구현하세요

 

class Solution {
    public int solution(int N, int K) {
        // 마지막으로 남은 사람의 번호를 구하는 함수 호출
        return josephus(N, K);
    }

    // 재귀적인 방법으로 요세푸스 문제를 해결하는 함수
    private int josephus(int n, int k) {
        if (n == 1) {
            return 1; // 마지막으로 남은 사람의 번호는 1
        } else {
            return (josephus(n - 1, k) + k - 1) % n + 1;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int N = 7;
        int K = 3;
        int result = solution.solution(N, K);
        System.out.println(result); // 출력 결과: 4 (마지막으로 남은 사람의 번호)
    }
}

주어진 문제는 N명의 사람들이 원형으로 모여서 순서대로 제외되는 과정을 K번째 사람을 제외하면서 반복하고, 마지막으로 남은 사람의 번호를 구하는 것입니다.

이 문제는 "요세푸스 문제(Josephus problem)"로 알려져 있으며, N명의 사람들이 원형으로 모여있을 때, K번째 사람을 제외하면서 반복적으로 제외하는 작업을 진행하여 마지막으로 남는 사람의 번호를 구하는 문제입니다.

요세푸스 문제는 재귀적인 방법으로 효율적으로 해결할 수 있습니다. 위 코드에서 사용한 josephus 함수는 재귀적인 방법으로 요세푸스 문제를 해결합니다.

1. josephus 함수:
   • 함수의 인자로는 n과 k가 주어집니다.
   • n은 현재 남은 사람들의 수를 의미합니다.
   • k는 K번째 사람을 의미합니다.
   • n이 1일 경우(남은 사람이 한 명일 경우), 마지막으로 남은 사람의 번호는 1이 됩니다. 따라서 1을 반환합니다.
   • n이 1보다 큰 경우, josephus(n - 1, k)를 호출하여 1명이 제외된 상태에서 K번째 사람을 제외하는 과정을 수행합니다.
   • 이후, (josephus(n - 1, k) + k - 1) % n + 1의 결과를 반환합니다.
   • 위 과정에서 (josephus(n - 1, k) + k - 1) % n는 현재 남은 사람들 중 K번째 사람의 인덱스를 구하는 과정입니다. 그리고 + 1을 통해 0-based 인덱스를 1-based 인덱스로 변환하여 마지막으로 남은 사람의 번호를 구합니다.

이렇게 재귀적인 방법으로 요세푸스 문제를 해결하면, 마지막으로 남은 사람의 번호를 효율적으로 구할 수 있습니다. Java의 재귀 호출은 내부적으로 스택을 사용하여 구현되기 때문에 큰 입력값에서도 적절한 성능을 보여줄 수 있습니다.