[LeetCode # 7 ~ 9] 문제 풀이

# 7. Reverse Integer

한 정수가 주어졌을 때, 자릿수를 뒤집은 정수를 반환하는 문제

ex) 12345 -> 54321

 

이 문제를 보고, 가장 먼저 떠올린 풀이는 정수를 한 자리씩 받아서 문자열로 변환하고, 이를 다시 정수형으로 바꾸는 거였다.

이렇게 하면, 1의 자리부터 문자열의 앞에서 넣으면 자연스럽게 뒤집을 수 있을 것이라 생각했다.

 

여기서 Solution 을 보고 참고했던 점은, 굳이 문자열로 변환했다가 다시 정수로 변환하는 과정을 거칠 필요 없이 새로운 정수에 10을 곱하고 기존 수의 1의 자리수를 새로운 정수의 1의 자리로 만들어주면 되는 점이었다.

그 다음으로 문제의 핵심은 오버플로우가 발생했을 때, 이 값을 어떻게 처리할 것인가. 였다.

 

이건 일일이 확인하는 방법이 가장 확실해 보였다. 새로운 수에 10을 곱하기 전에 조건을 확인하고 진행을 할 수 있도록 했다.

 

#define INT_MAX 2147483647
#define INT_MIN -2147483648

class Solution {
public:
	int reverse(int x) {
		int rev = 0;
		while (x != 0) {
			int pop = x % 10;
			x /= 10;
			if (rev > INT_MAX / 10 || (rev == INT_MAX / 10 && pop > 7)) return 0;
			if (rev < INT_MIN / 10 || (rev == INT_MIN / 10 && pop < -8)) return 0;
			rev = rev * 10 + pop;
		}
		return rev;
	}
};

# 8. String to Integer (atoi)

atoi 함수를 직접 구현하는 문제

 

이 때 문제의 조건은, 숫자 앞의 공백은 무시하고 '+' / '-' 는 결과값의 부호를 의미하는 것이다.

문자열에서 숫자의 조건은, 처음으로 숫자가 나와서 숫자 이외의 문자가 등장하기 전까지이고 숫자가 아닌 문자가 앞에 있는 경우 숫자로 인식하지 않는다.

추가로 오버플로우가 발생할 경우, 오버플로우가 발생하지 않는 최대(최소)값을 반환하도록 한다.

 

이 문제는, 위의 문제 풀이를 참고해서 오버플로우 조건을 검사하도록 하고, 문자열을 숫자로 변환하는 건 앞에서부터 하도록 했다.

 

class Solution {
public:
    int myAtoi(string s) {
        int idx = 0, ret = 0;
        while (s[idx] == ' ') {
            idx++;
        }

        bool negative = false;
        if (s[idx] == '-') {
            negative = true;
            idx++;
        }
        else if (s[idx] == '+')
            idx++;

        while (s[idx] >= '0' && s[idx] <= '9') {
            if (negative && (ret > INT_MAX / 10 || (ret == INT_MAX / 10 && s[idx] >= '8'))) {
                return INT_MIN;
            }
            if (!negative && (ret > INT_MAX / 10 || (ret == INT_MAX / 10 && s[idx] >= '7'))) {
                return INT_MAX;
            }
            ret = ret * 10 + (s[idx] - '0');
            idx++;
        }

        return (negative ? -ret : ret);
    }
};

# 9. Palindrome Number

주어진 정수가 Palindrome Number 인지 확인하는 문제

Palindrome Number 란, 앞뒤 자리가 대칭되는 수 ex) 12345 (X), 12321 (O)

 

처음 생각은, Palindromic String 처럼 가운데 위치를 잡고 그 위치 앞뒤로 대칭인지를 확인하는 방식이었다. 

하지만 정수는 가운데가 어디인지 한 번에 찾는 게 불가능해서 다른 방식을 찾게 되었다.

 

Solution 을 참고해 얻은 결과는, #7 번 문제를 참고해서 숫자를 뒤집는 중간에 자리수가 같거나 한자리 차이나는 순간에 두 수를 비교하면 앞뒤가 대칭인지 알 수 있다는 것이었다.

 

class Solution {
public:
	bool isPalindrome(int x) {
		if (x < 0 || (x != 0 && x % 10 == 0))
			return false;

		int rev = 0;
		while (x > rev) {
			rev = rev * 10 + x % 10;
			x /= 10;
		}

		return rev == x || x == rev / 10;
	}
};