리트코드 - Reverse Integer

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

Reverse Integer - LeetCode

32비트 정수 x를 반환받았다고 가정했을 때, 부호는 유지한 상태에서 해당 정수를 역순으로 반환한 값을 출력하면 된다.

이때 유의해야 할 점은 64비트 정수일 경우 오버플로우이기 때문에 0을 출력하여야 한다는 조건이다.

 

관련 문제를 풀다보니 이전이었으면 문자열로 변환 -> 역순으로 변환을 하는 간단한 방식을 시도했을 것이다. 그리고 코드 자체는 명료할 것이다.

 

하지만 공간 복잡도의 관점에서 볼 때 문자열로 변환할 경우, 만약 x가 매우 큰 숫자일 경우 이를 할당하기 위해 문자열 변수를 추가로 할당할 경우 공간 복잡도는 입력 크기에 따라 O(n)이 될 수 있다. 따라서 이에 대해서 문자열로 변환하는 추가적인 메모리를 할당하는 것은 불필요한 메모리 할당이 될 것이다.

 

이를 위해서 입력받은 숫자를  문자열 변환을 사용하지 않고 숫자를 반복적으로 나누어 뒤집은 숫자를 구성하는 방식을 사용했다.

그리고 부호는 유지하여야 하기 때문에 사전에 음수 여부를 파악하고 그 여부를 저장하는 변수 is_minus를 할당했다.

class Solution:
    def reverse(self, x: int) -> int:
        INT_MAX, INT_MIN = 2**31 -1, -2**31
        is_minus = x < 0
        reversed_num = 0
        x = abs(x)
        while x > 0:
            reversed_num = reversed_num * 10 + x % 10
            x //= 10
            if reversed_num > INT_MAX or reversed_num < INT_MIN:
                return 0
        return -reversed_num if is_minus else reversed_num

 

여기서 시간 복잡도는 최악의 경우 O(n)이 되겠지만, 오버플로우 여부를 역순으로 변환할 때 마다 확인함으로써 실행시간을 최소화하고자 하였다.