LeetCode 1823. Find the Winner of the Circular Game 자바 문제 풀이

문제 설명

• 문제: LeetCode 1823. Find the Winner of the Circular Game
• 설명: 1부터 n까지 번호가 붙은 n명의 사람이 원형으로 앉아 있습니다. 이 게임은 k번째 사람을 제거하는 방식으로 진행되며, 마지막 한 사람이 남을 때까지 계속됩니다. 최종 승자의 번호를 반환하세요.

접근 방식

• 아이디어:
  • 조세퍼스 문제(Josephus problem)로 알려진 문제입니다.
  • 원형 리스트에서 매 k번째 사람을 제거하는 과정을 반복하여 최종 승자를 찾습니다.
• 알고리즘:
  1. LinkedList를 사용하여 1부터 n까지의 숫자를 저장합니다.
  2. 현재 제거할 사람의 위치를 추적하기 위해 removeMarker 변수를 사용합니다.
  3. 리스트의 크기가 1이 될 때까지 다음 과정을 반복합니다:
     • removeMarker를 (현재 removeMarker + k - 1) % 리스트의 크기로 업데이트하여 제거할 사람의 인덱스를 계산합니다.
     • k번째 사람이 다음에 제거할 사람입니다.
     • -1을 하면 인덱스를 알수 있습니다.
     • % 리스트의 크기를 해서 원형으로 계산할수 있습니다.
     • 해당 인덱스의 사람을 리스트에서 제거합니다.
  4. 최종적으로 남은 한 사람의 번호를 반환합니다.

코드

class Solution {
    public int findTheWinner(int n, int k) {
        LinkedList<Integer> list = new LinkedList<>();
        int removeMarker = 0;
        for (int i = 0; i < n; i++) {
            list.add(i + 1);
        }

        while (list.size() > 1) {
            removeMarker = (removeMarker + k - 1) % list.size();
            list.remove(removeMarker);
        }
        return list.get(0);
    }
}

결론

• 시간 복잡도:
  • 리스트에서 요소를 제거하는 작업은 O(n)의 시간이 소요되므로, 전체 알고리즘의 시간 복잡도는 O(n^2)입니다.
• 공간 복잡도:
  • 추가적인 공간으로 LinkedList를 사용하며, n개의 요소를 저장하므로 O(n)입니다.

접근 방식 2

• 아이디어:
  • 수학적으로 봤을때, 이미 n과 k가 정해진 시점에서 제거될 인덱스는 정해져있습니다.
  • 이는 수열의 역순 연산이라고 부릅니다. 특정 규칙을 따르는 반복적인 연산에서, 시작점과 끝점을 뒤바꾸어도 같은 결과를 얻는 경우를 말합니다.
    • 대칭성 (Symmetry): 대칭성은 수학적 구조나 문제의 성질이 방향에 관계없이 동일하게 유지되는 성질을 말합니다. 조세푸스 문제에서 루프의 방향을 바꿀 수 있는 이유는 문제의 본질이 방향에 무관하기 때문입니다. 즉, n명의 사람들 중에서 k번째 사람을 제거하는 규칙이 방향에 상관없이 동일하게 적용되기 때문입니다.
    • 순환성 (Circularity):조세푸스 문제는 원형 배열에서 시작하는 문제입니다. 원형 배열에서는 순서가 순환적으로 이어지므로, 처음과 끝의 개념이 명확하지 않습니다. 이 순환성 덕분에, 문제의 해결 방법이 처음부터 시작하든 끝에서부터 시작하든 동일한 결과를 얻게 됩니다.
    • 예시 설명: 조세푸스 문제를 해결할 때, for (int i = 2; i <= n; i++)에서 for (int i = n; i > 1; i--)로 변경해도 동일한 결과가 나오는 이유는, 각 단계에서의 계산이 순환적이고 대칭적인 성질을 가지기 때문입니다.
      • 순환성: 원형 배열에서의 제거 규칙이 순환적이므로, 시작점을 어디로 잡아도 동일한 결과가 나옵니다.
      • 대칭성: 순서와 상관없이 동일한 계산을 반복하므로, 루프의 방향을 바꿔도 결과는 변하지 않습니다.
  • 즉, 인덱스를 계산하여, 남겨진 요소(사람)의 개수에 따라 몇번째 인덱스의 요소(사람)이 제거될지 계산할수 있습니다.
  • 리스트를 순회하며 요소(사람)을 제거합니다.
• 알고리즘:
  1. winner 변수를 0으로 초기화합니다. 이는 0번 인덱스부터 시작하는 것을 의미합니다.
  2. 1명인경우 답이기때문에, 2명부터 n명까지 반복하면서, 매 반복마다 현재의 승자를 다음 사람으로 갱신합니다.
     • k번째 사람이 다음에 제거할 사람입니다.
     • 인덱스로 계산하므로, -1를 할 필요가 없습니다.
     • % i 에서 i는 리스트의 크기(남겨진 사람)을 뜻합니다. 이를 계산해서 원형으로 계산할수 있습니다.
     • 해당 인덱스의 사람을 리스트에서 제거합니다.
  3. 마지막으로 winner에 1을 더하여 인덱스의 값을 반환합니다.

코드

class Solution {
    public int findTheWinner(int n, int k) {
        int winner = 0;
        for (int i = 2; i <= n; i++) {
            winner = (winner + k) % i;
        }
        return winner + 1;
    }
}

결론

• 시간 복잡도:
  • 루프는 n-1번 반복되므로 O(n-1)입니다.
• 공간 복잡도:
  • 상수 공간만 사용하므로 O(1)입니다.

접근 방식 3

• 아이디어:
  • 접근방식 2와 같습니다.
  • 단 이를 루프가 아니라 재귀함수를 사용하여 접근합니다.
• 알고리즘:
  1. 기본 케이스로 n이 1일 때, 0을 반환합니다.
  2. 그 외의 경우, (findTheWinnerRecur(n - 1, k) + k) % n을 반환합니다.
  3. 재귀적으로 호출하여 최종적으로 승자의 인덱스를 찾습니다.
  4. 인덱스가 0부터 시작하므로 1을 더하여 인덱스의 값을 반환합니다

코드

class Solution {
    public int findTheWinner(int n, int k) {
        return findTheWinnerRecur(n, k) + 1;
    }

    private int findTheWinnerRecur(int n, int k) {
        if (n == 1) return 0;

        return (findTheWinnerRecur(n - 1, k) + k) % n;
    }
}

결론

• 시간 복잡도:
  • 재귀 함수는 n번 호출되므로 O(n)의 시간이 소요됩니다.
• 공간 복잡도:
  • 재귀 호출에 의해 스택에 저장되는 호출의 깊이는 최대 n이므로 O(n)의 공간이 필요합니다.