[Leetcode][C++][난이도 Easy] Palindrome Number

오늘의 두번째 문제는 leetcode의 난이도 easy 두번째 문제 palindrome number입니다. Palindrom number가 무슨 숫자인지 살펴보고, 문제 분석, 문제 해결을 위한 C++ 코드, 제일 많은 추천을 받은 코드도 살펴보겠습니다.

 

Palindrom number의 정의

 

[사진 1] Palindrom number의 수학적 정의 (출처: 위키피디아)

 

사실 palindrom number라고 했을 때, 무슨 숫자인지 몰라서 wikipedia를 검색해봤습니다. 아래 palindrom number의 수학적 정의와 같이, 순서대로 읽은 수와 거꾸로 읽은 수가 동일한 경우를 의미하고, 한국어로 '대칭수'라는 것을 알았습니다. 마치 "거꾸로 해도 이효리~"라고 말하는 것처럼.. (죄송합니다). 아무튼, 수식에서 제일 큰 핵심은 위 [사진 1]의 빨간색 밑줄을 친 부분인데요, 이걸 프로그램에서 어떻게 구현할지가 관건이라고 생각했었습니다.

 

 

Palindrom number 문제 분석

 

[사진 2] Leetcode Palindrom number 문제

 

그러면 문제를 살펴보겠습니다. 나중에 또 언급하겠지만, 따봉이 역따봉보다 훨씬 많을수록 좋은 문제, 역따봉이 훨씬 많을수록 퀄리티가 떨어지는 문제(?)라고 합니다. 이 문제는 그래도 좋은 문제군요. 주어진 x가 palindrome number라면 true, 아니면 false를 반환하는 것이 목표입니다. 예제를 보니 "121"은 거꾸로 해도 "121"이니까 true 입니다. 하지만 두번째 예제에서 -121 의 경우, 거꾸로 하면 "121-"가 되버리니까 false 라고 합니다. x가 음수일 때도 처리를 해야겠군요. 마지막으로 세번째 예제는 "10"이니까 거꾸로 하면 "01"이라서 false이여야 합니다. 맨 밑에 follow up을 확인해보니, string으로 바꾸지 않고 integer만 사용해서 문제를 해결해볼 수 있는지 물어보고 있는데요, 결국 integer로도 충분히 해결될 수 있다라는 힌트를 넌지시 보여주고 있습니다.

 

 

Palindrom number 문제 해결을 위한 C++ 코드

 

#include <vector>

class Solution {
public:
    bool isPalindrome(int x) {
        bool result = false;
        int flag = 0;
        vector<int> a_list;
        
        if ( x >= 0)
        {
            while ( x != 0)
            {
                int temp = x % 10;
                a_list.push_back(temp);
                x /= 10;
            }
            
            for (int i = 0; i < (a_list.size() / 2); i++)
            {
                if (a_list[i] != a_list[a_list.size()-i-1])
                {
                    flag = 1;
                    break;
                }
            }
        
            if (flag == 0)
                result = true;
        }
        
        return result;
    }
};

 

제가 생각했던 방법은 아래의 두 단계에 걸쳐서 해결하는 방법이었는데요, 우선 입력받은 숫자의 맨 앞과 맨 뒤의 숫자가 동일한지 확인하고, 점점 가운데로 접근하면서 두 숫자가 동일한지 아닌지를 확인하는 방법이었습니다. 사실 [사진 1]의 빨간 선으로 표시된 조건문을 그대로 구현한 것이 전부였습니다.

 

1. 현재 입력받은 숫자 x 의 각 자릿수를 vector에 순차적으로 저장 

2. 1의 vector의 맨 앞과 끝의 숫자를 비교해서, palindrom number인지 확인 

 

위 [사진 2]는 위에서 제가 생각했던 해결방법을 구현해본 코드입니다. 최종결과인 result는 false로 초기화를 시켜주고, if 문에서 입력받은 x가 음수라면, 바로 result를 반환해줍니다. 그러면 false가 반환되겠죠? 그리고 integer 타입 변수 flag는 0으로 초기화를 시켜주고, 나중에 양 끝의 수를 비교했을 때 서로 다르면, 이 flag가 1이 되면서, false로 반환되게 하는 역할을 수행합니다. 

 

이제 x가 양수일 때의 처리 과정을 살펴볼까요? 우선 x가 0이 아닐 때까지 a_list라는 vector에 일의 자리 수부터 push_back을 통해 순차적으로 x의 모든 숫자를 저장합니다. 이후, vector의 0번째부터 vector size의 절반에 해당하는 인덱스만큼 loop을 수행하면서, vector의 i 번째 숫자와 (vector의 크기 - i - 1) 번째 숫자를 비교합니다. 만약 전부 같은 수였다면, flag는 0이었기 때문에, result는 true가 되면서 최종적으로 true가 반환되겠네요. 하지만 만약 다른 수를 찾았다면? 구지 모든 for loop을 돌릴 필요없이, break로 탈출해서 false를 반환하면 됩니다.

 

 

Palindrom number 문제의 솔루션 코드 중 제일 많은 추천을 받은 코드

 

class Solution {
public:
    bool isPalindrome(int x) {
        if(x<0|| (x!=0 &&x%10==0)) return false;
        int sum=0;
        while(x>sum)
        {
            sum = sum*10+x%10;
            x = x/10;
        }
        return (x==sum)||(x==sum/10);
    }
};

 

이제 다른 사람의 코드도 살펴봅시다. 한눈에 봐도 제 코드보다 더 깔끔한 것 같죠? (사실 저도 제 코드보다 잘하는 분들의 코드를 보는 것이 더 재밌습니다 ㅎㅎ;) 우선 첫 if 문에서는 x가 음수인지 체크해서 false를 바로 반환합니다. 그리고 여기서 제가 놀랐던 부분인데요, x 가 0이 아니고, x의 일의 자리 숫자가 0이면 false를 반환하고 있습니다. 사실 일의 자리 숫자가 0일 때 palindrom number이기 위해서는, 숫자의 맨 앞에 0이 존재해야 하죠. 하지만 210 을 012로 바꿀 때, 12가 되버리죠. 그러니까, 아무리 큰 숫자라도 일의 자리가 0이면 바로 false입니다. 이렇게 되면 불필요한 for loop 연산 수행도 할 필요가 없습니다.

 

if 문에 걸리지 않은 숫자라면, 이제 본격적으로 palindrome number인지 체크하는 loop을 수행합니다. 이 부분도 저와 다른 포인트인데요, 저는 vector에다가 x의 모든 숫자를 저장하고, 이 vector의 인덱스를 이용해서 숫자를 비교한 반면, 여기서는 while loop 한 번에 끝나버립니다. while loop을 보시면, rev는 결국 x의 역순으로 된 숫자들을 차례대로 저장하고 있습니다. 예를 들어, x가 123 이라면, 321이 rev에 저장되겠지요. 다른 예로 x가 11211 이라면, rev에는 11211이 저장됩니다. 이후 return을 해줄 때 x와 rev가 서로 동일하거나, x와 (rev / 10)이 동일한지를 확인해서 결과를 반환합니다. 이 둘 중 하나가 true라면 true가 반환되겠죠?

 

 

지금까지 leetcode의 두번째 easy 문제였던 palindrome number를 C++로 풀어보는 시간을 가져보았습니다. 역시 잘하는 분들의 코드를 보면 저 스스로 갈 길이 멀다고 생각합니다. 하지만 매일 노력하고, 끊임없이 고민해서 문제를 풀어보려는 시도가 정말 중요하다고 생각됩니다. 그러면 다음에 또 찾아 뵙겠습니다.