Reverse Integer

Reverse Integer

|| 문제설명 ||

1. 32비트의 정수(-2^31 <= x <= 2^31 - 1)를 반전시켜 리턴하세요.
2. 만약 반전된 정수에서 Integer Overflow이 발생한다면 0을 리턴하세요.

• Input

  int x

• Output

  int

---

|| 문제해결과정 ||

int reversedX

- x == 0일 때
- 음수인지 양수인지
	bool sign = (x < 0) ? false : true;
    	sign(-)가 필요한지 안필요한지
        
- 반전했을 때 앞에 0이 올 경우
	bool start = false;
    	처음으로 0이 아닌 숫자를 만나면 true

주의해야할 점

---

[2020.11.14] 실패

class Solution {
public:
    int reverse(int x) {
        bool start = false, sign = (x < 0) ? true : false;
        int reversedX = 0, length = 1;
        
        if(x == 0) return 0;
        if(sign) x *= -1;
        
        int tmp = x;
        while(tmp >= 10) {
            length *= 10;
            tmp /= 10;
        }
        
        while(x > 0) {
            if(!start && x % 10) start = true;
            
            if(start) {
                reversedX += length * (x % 10);
            }
            length /= 10;
            x /= 10;
        }
        if(sign) return reversedX*-1;
        return reversedX;
    }
};

"reversedX += length * (x % 10)" 을 연산하는 과정에서 오버플로우 발생

해당 값이 int의 범위 안인지 아닌지 확인하여 0리턴

---

[2020.11.14] 실패

class Solution {
public:
    int reverse(int x) {
        bool start = false, sign = (x < 0) ? true : false;
        long reversedX = 0, length = 1;
        
        if(x == 0) return 0;
        if(sign) x *= -1;
        int tmp = x;
        while(tmp >= 10) {
            length *= 10;
            tmp /= 10;
        }
        
        while(x > 0) {
            if(!start && x % 10) start = true;
            
            if(start) {
                if(((reversedX+length * (x % 10)) > INT_MAX) || ((reversedX +length * (x % 10)) < INT_MIN)) return 0;
                reversedX += length * (x % 10);
            }
            length /= 10;
            x /= 10;
        }
        if(sign) return (int)reversedX*-1;
        return (int)reversedX;
    }
};

"x *= -1"에서 x가 INT_MIN인 경우 -1을 곱하면 INT_MAX보다 큰 값이 되므로 오버플로우가 발생한다.

애초에 (x == INT_MIN) 이라면 0을 리턴한다. 뒤집어도 무조건 오버플로우라서 상관없다.

---

[2020.11.14] 성공

class Solution {
public:
    int reverse(int x) {
        bool start = false, sign = (x < 0) ? true : false;
        long long reversedX = 0, length = 1;
        
        if(x == 0 || x == INT_MIN) return 0;    // 오버플로우 캐치

        if(sign) x *= -1;
        
        int tmp = x;            // x의 길이 구하기
        while(tmp >= 10) {
            length *= 10;
            tmp /= 10;
        }
        
        while(x > 0) {
            if(!start && x % 10) start = true;
            
            if(start) {
                if(((reversedX+length * (x % 10)) > INT_MAX) || ((reversedX +length * (x % 10)) < INT_MIN)) return 0;   // 오버플로우 캐치
                reversedX += length * (x % 10);
            }
            length /= 10;
            x /= 10;
        }
        if(sign) return (int)reversedX*-1;
        return (int)reversedX;
    }
};

---

단순 구현 문제라 시간 복잡도는 별 신경안쓰지만 공간복잡도가 별로 많이 좋지 못하다.

난이도가 쉬움에도 불구하고 성공률이 낮았던 이유는 오버플로우를 해결하는 과정이 필요하기 때문이었던 것이었다.

---

|| 코드 정리||

class Solution {
public:
    int reverse(int x) {
        bool sign = (x < 0) ? true : false;
        long reversedX = 0;
        
        if(x == 0 || x == INT_MIN) return 0;  

        if(sign) x *= -1;
        
        while(x > 0) {
            if((reversedX * 10 + (x % 10)) > INT_MAX) return 0;   // 오버플로우
            reversedX = reversedX * 10 + (x % 10);
            x /= 10;
        }
        return (sign) ? reversedX * -1 : reversedX;
    }
};

---

- 음수도 양수와 똑같이 연산된다.
	>> 굳이 sign변수를 사용하지 않고도 바로 연산가능하다.

[2020.11.14]

class Solution {
public:
    int reverse(int x) {
        long long reversedX = 0;

        while(x != 0) {
            reversedX = reversedX * 10 + (x % 10);
            x /= 10;
        }
        return (reversedX > INT_MAX || INT_MIN > reversedX) ? 0 : reversedX;
    }
};