<Medium> Integer Replacement (LeetCode : C#)

https://leetcode.com/problems/integer-replacement/

📕 문제 설명

정수가 주어졌을 때 1로 만들기 위한 최소 연산 수 반환
연산은 다음 2가지로 구성
1) 짝수일 경우 n / 2
2) 홀수일 경우 n + 1 또는 n - 1

• Input
  정수
• Output
  정수를 1로 만들기 위한 최소한의 연산 수

예제

시도 1.

n 범위 보니 재귀로 하면 stack overflow 날 것 같았는데 역시나..

public class Solution {
    public int IntegerReplacement(int n) {

        return GetOperationCount(n, 0);
    }

    public int GetOperationCount(int n, int count)
    {
        int evenCnt = Int32.MaxValue;
        int oddCnt = Int32.MaxValue;
        if (n == 1)
        {
            return count;
        }

        if (n % 2 == 0)
        {
            evenCnt = GetOperationCount(n / 2 , count + 1);
        }
        else
        {
            oddCnt = Math.Min(GetOperationCount(n + 1, count + 1), GetOperationCount(n - 1, count + 1));
        }

        return Math.Min(evenCnt, oddCnt);
    }
}

풀이 1.

int max 부분만 처리하면 위의 풀이로 통과가 된다.

public class Solution {
    public int IntegerReplacement(int n) {
        if (n == Int32.MaxValue) return 32; 
        return GetOperationCount(n, 0);
    }

    public int GetOperationCount(int n, int count)
    {
        int evenCnt = Int32.MaxValue;
        int oddCnt = Int32.MaxValue;
        if (n == 1)
        {
            return count;
        }

        if (n % 2 == 0)
        {
            evenCnt = GetOperationCount(n / 2 , count + 1);
        }
        else
        {
            oddCnt = Math.Min(GetOperationCount(n + 1, count + 1), GetOperationCount(n - 1, count + 1));
        }

        return Math.Min(evenCnt, oddCnt);
    }
}

결과 1.

풀이 2.

메모이제이션 사용한 방법 (top - down)
위랑 비슷한데 케이스 별로 dictionary에 저장해둬서 반복되는 재귀 피하도록

public class Solution {
    Dictionary<int, int> memo;
    public int IntegerReplacement(int n) {
        memo = new Dictionary<int, int>();
        return GetCounts(n);
    }

    private int GetCounts(int n)
    {
        if(n == 1) return 0;
        if(memo.ContainsKey(n)) return memo[n];
        if(n%2 == 0) return 1+GetCounts(n/2);
                 
        int answer = 0;
        if(n != Int32.MaxValue) answer = Math.Min(GetCounts(n+1), GetCounts(n-1)) + 1;
        else answer = GetCounts(n-1); // int max에서는 더하면 안됨 
        if(!memo.ContainsKey(n)) memo.Add(n, answer);
        return answer;
    }
}

결과 2.