[LeetCode] 9. Palindrome Number (C++)

https://leetcode.com/problems/palindrome-number?envType=problem-list-v2&envId=math

Palindrome Number - LeetCode

 

Palindrome이란 우리말로 "회문( 回文)"이라고 하며,

 

앞으로 읽으나 뒤로 읽으나 그 내용이 같은 단어, 문장, 숫자, 또는 문자열을 의미한다.

 

예를 들자면,

 

기러기, 토마토, 스위스, level, radar, madam, 121, 4554, 1234321, 7.... 이런걸 말한다.

 

 

LeetCode, 9. Palindrome Number

문제는 간단하다. 

 

Integer 입력 x가 들어오면, x가 Palindrome 조건을 만족하면 true, 그렇지 않다면 false를 반환한다. 

 

이때 x가 Palindrome인지 아닌지 판단하는 함수를 채워 넣어주면 된다.

 

이 문제의 난이도는 Easy인데, 아래 Follow up을 보면 integer를 string으로 바꾸지 않고 풀수 있냐고 써져있다.

그래서 integer만 이용해서 풀어보도록 하겠다.

 

일단 문자열로 변환하여 비교하는 것은, 

숫자를 문자열로 바꾼 뒤, 첫 글자와 마지막 글자부터 차례대로 비교하며 안쪽으로 들어오는 방식으로 풀면 될 것 같다.

 

로직 흐름은 간단하기 때문에 금방 풀 수 있을 것이다.

#include <string>
#include <algorithm>

bool isPalindrome(int x){
	string s = to_string(x); // 숫자를 문자열로 변환
    int left = 0, right = s.length() - 1; // Two pointers alogorithm
    // left는 0번 idx, right는 끝 idx에서 시작
    
    // 서로 가리키는 문자가 다르면 false, 중간에서 만날 때까지 같으면 true를 반환한다.
    while(left < right){
    	if(s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
}

 

이제 숫자를 직접 뒤집어서 비교를 해보도록 하자.

 

숫자를 문자열로 바꾸지 않고, 산술 연산(%, /)만 사용해서 숫자를 뒤집는 방식이다. 이 방법은 메모리 사용량이 적어서 위 방식보다 효율적이다.

 

먼저 로직 흐름은 다음과 같다.

 

1. 먼저 무조건 Palindrome이 아닌 경우를 처리해준다. 음수이거나, 0이 아닌데 0으로 끝나는 숫자는 Palindrome일 수가 없다.

2. 다음은 숫자 뒤집기이다. 원본 숫자를 10으로 나눈 나머지(%)를 이용해서 끝자리부터 하나씩 떼어내어 새로운 숫자를 만든다.

3. 그리고 뒤집은 숫자와 원본 숫자가 같으면 Palindrome이 되는 것이다.

class Solution {
public:
    bool isPalindrome(int x) {
        //음수이거나, 0이 아닌데 0으로 끝나는 숫자는 Not Palindrome
        if(x<0 || (x&10 ==0 && x!= 0)) return false;

        long long reversedNum = 0; //뒤집힌 숫자가 int 범위를 넘을 수 있어 long long을 사용
        int original = x;

        while(x>0){
            reversedNum = reversedNum * 10 + (x % 10);// 10진수 좌로 shift, + 원본 나머지 연산으로 마지막 일의 자리 숫자 추출
            x /= 10; // 10진수 우측 shift
        }

        return original == reversedNum;
    }
};