[LeetCode | Python] 397. Integer Replacement

느낀점

약간의 수학적 트릭이 있는 경우 잘 감안해서 로직을 작성해야 한다.

문제

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

주어진 양의 정수 n에 대해 다음 연산 중 하나를 적용한다.

• n이 짝수면, n을 n / 2로 바꾼다.
• n이 홀수면, n을 n + 1 또는 n - 1로 바꿉니다.

목표는 n을 1로 만드는 데 필요한 최소 연산 횟수를 반환하는 것

풀이

문제를 보면 구현하는 것은 어렵지 않은데, 홀수일 때 언제 n+1, n-1을 해야하는지 고려해야 한다. 이 부분은 n = 3일 때, 그리고 n이 4의 배수보다 하나 더 클 때, n에서 1을 빼야 하고 나머지 홀수는 그냥 하나를 추가하는 것으로 구현했다. 중요한 것은 왜 3일 때, 그리고 4의 배수보다 1이 클 때 1을 빼는가이다.

 

1. 3인 경우

3에서 +1을 하게 되면 4가 되고 4 -> 2 -> 1 이 되어 2 -> 1보다 한 횟수 더 많다. 따라서 3인 경우에 -1이 맞다.

 

2. 4의 배수 + 1인 경우

2로 나눌 때 1로 가는 최소 연산 수는 2의 배수일 때일 것이다. 따라서, n이 4의 배수에서 1 차이나는 경우 1을 빼어 4의 배수를 맞춰준다.

class Solution:
    def integerReplacement(self, n: int) -> int:
        cnt = 0
        
        while n > 1:
            if n % 2 == 0:
                n //= 2
            elif n == 3 or n % 4 == 1:
                n -= 1
            else:
                n += 1
            cnt += 1
        
        return cnt

 

결과

• 공간복잡도: $$ O(1) $$
• 시간복잡도: $$ O(LogN) $$