[코딩테스트 일지 - 99클럽] 13일차 - Divisor Game

코딩 테스트 준비 일지 13 일차

• 응시 사이트 : LeetCode

• 문제 : Divisor Game

• 난이도 : 중상 ( 체감 중상.. )

• 풀이시간 : 2h 43m

문제 설명

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there is a number n on the chalkboard. On each player's turn, that player makes a move consisting of:

• Choosing any x with 0 < x < n and n % x == 0.

• Replacing the number n on the chalkboard with n - x.

Also, if a player cannot make a move, they lose the game.

Return true if and only if Alice wins the game, assuming both players play optimally.

 Example 1:

Input: n = 2
Output: true
Explanation: Alice chooses 1, and Bob has no more moves.

Example 2:

Input: n = 3
Output: false
Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.

 Constraints:

• 1 <= n <= 1000

문제 풀이 접근

일단, 문제 풀이에 앞서 LeetCode 와 HackerRank 같은 외국사이트는 정확한 요구조건을 파악하는게 먼저다. 또 이상한 해석으로 삽질할 것이라고 생각해서 먼저 해석해본 뒤에 번역기로 체크까지하고 시작했다.

요구조건은 다음과 같다.
1. n 이라는 자연수를 주겠다. 범위는 1 <= n <= 1000
2. 한 턴씩 숫자를 변화시켜야 한다. n = (n -x) 로 변화해야한다.
(x 의 범위는 0 < x < n , 조건은 n % x == 0 )
3. n 을 더이상 대체할 수 없으면 게임은 종료한다.
4. Alice 부터 시작한다.
5. 앨리스가 이긴다면 True 한다. 이외는 False ( 패배하면 False 겠지..)

문제를 또 여기서 이해를 못해서 도저히 문제가 잘못됐다고 판단했는데 n 를 n -x 로 대체하는것을 또 까먹고 삽질했다. 문제 잘 읽어야한다.

나는 여기서 활용한 것은 일단 메모이제이션을 활용하면 좋겠다고 생각했고, 재귀함수를 만들어서 이 결과를 배열로 저장하면 속도를 더 빠르게 처리할 수 있을것이라고 생각했다.

문제 해결 플로우는 아래와 같다.
1. 배열을 만든다. n 의 제한이 1000 까지니까 1001 짜리 배열을 만들어서 초기화한다.
2. 앞 수들은 미리 배열에 넣었다. ( 앞 수 : 0,1,2,3 등 바로 확인할 수 있는 수들은 바로 넣어줬다. )
앞 수 : 0 -> False, 1 -> False, 2 -> True, 3 -> False 등
3. 메모이제이션 한 값을 가져와 보고 False면 결과가 False라도 다시한면 MakeResult 함수로 만들어준 뒤에 결과를 재확인한다.
4. MakeResult 는 1이 되면 종료하는 재귀함수이며 이 함수의 반환값 자체가 Alice 의 사용턴이라고 이해할 수 있다. ( 앨리스는 홀수턴에만 이긴다. )
5. MakeResult 함수 안에서도 들어온 n 의 값은 계속해서 변화하며, 그때그때 뽑을 수 있는 수가 다르기 때문에 MakeSelectNumber로 리스트를 만들어서 넣어준다. 가능한 한 모든 경우의 수를 다 파악해서 넣는것이 정확한 결과를 만들어낸다.
6. 반환하여 돌아오는 값을 배열에 저장하고, 저장한 배열의 값을 가져와서 함수 종료한다.

정답 작성 코드 ( C++ )

    public class Solution
    {

        public int nMax = 1001;
        public bool[] result;
        public static int Number;

        public bool DivisorGame(int n)
        {
            Init(); // 결과 메모이제이션이라 상관없을 듯,
                    // 0 < x < n , n % x == 0 

            Number = n; 

            if (Number == 0) return false;
            if (Number == 1) return false;
            if (Number == 2) return true;
            if (Number == 3) return false;

            if (TryGetResult(Number) == true)
                return true;

            result[Number] = MakeResult(Number);
            return result[Number];
        }

        public bool MakeResult(int n) // adding 는 가중, count는 
        {
            if (n == 1)
                return false;

            List<int> SelectedNumbers = new List<int>();

            MakeSelectedNumber(n, ref SelectedNumbers);

            for (int i = 0; i < SelectedNumbers.Count; ++i)
            {
                if (0 >= n - SelectedNumbers[i]) continue;
                return !MakeResult(n - SelectedNumbers[i]);
            }

            return false;
        }

        public void MakeSelectedNumber(int n, ref List<int> selectedNumber)
        {
            for (int i = 0; i < n; ++i)
            {
                if (i == 0) continue;
                if (n % i == 0)
                    selectedNumber.Add(i);
            }
        }


        public void Init()
        {
            result = new bool[nMax];

            result[0] = false; // 있을리도 없지만, False 처리
            result[1] = false; // 앨리스가 선택할 수 없기때문에 false,
            result[2] = true;
            result[3] = false; // 앨리스 패배
        }

        public bool TryGetResult(int n)
        {
            return result[n];
        }
    }

코드 결과