[Leetcode/Easy] 9. Palindrome Number

앞 뒤가 똑같은 경우 ture를 다른 경우 false를 output으로 출력 해 주는 문제다.

 

문제를 보고 엉뚱하게 stack이 먼저 생각났다.

깊이 생각안하고 바로 풀었던 솔루션은 다음 과 같다.

 

char 배열에 값을 넣어두고 중간까지만 stack에 넣은 뒤 pop되는 값과 array 값을 비교해 준다.

 

class Solution {
public:
    bool isPalindrome(int x) {
        char v = 0;
        
        char arr[10] = {0, };
        int arr_len = 0;
        
        if (x < 0)
            return false;
        
        while ( true ) {
            v = x % 10;
            x /= 10;
            
            arr[arr_len++] = v;
                
            // 1 / 10 == 0;
            if ( x == 0 )
                break;
        }
        
        // push stack
        stack<int> stack;
        
        for ( int i = 0; i < arr_len / 2; i++ ) {            
            stack.push( (int)arr[i] );    
        }
        
        // pop stack        
        int start_index = arr_len / 2;
        
        if ( arr_len % 2 == 1)
            start_index += 1;  
    
        for ( int i = start_index; i < arr_len; i++ ) {
            
            int val_1 = stack.top();
            int val_2 = arr[i];
            
            if ( val_1 != val_2 )
                return false;            
            
            stack.pop();
        }
            
        return true;
    }
};

 

Accept 결과가 엄청나게 느린 걸 보고 한번 다시생각해보니 그냥 Array에서도 충분히 비교가 가능했다.

배열의 장점이 index로 접근할 수 있다는 것인데 그 부분을 아예 생각하지 않았던 게 아닌가 싶다.

 

그래서 아래와 같이 고쳤다.

 

class Solution {
public:
    bool isPalindrome(int x) {
        
        if (x < 0)
            return false;
                
        char arr[10] = {0, };
        int arr_len = 0;
        
        while ( true ) {
            arr[arr_len++] = x % 10;
            x /= 10;
            
            if ( x == 0 )
                break;

        }
                
        int mid = arr_len / 2;
        
        for ( int i = 0; i < mid ; i++ ) {                        
            if ( arr[i] != arr[arr_len - i - 1] )
                return false;
        }        
        
        return true;
    }
};

 

그래도 조금은 일반적인(?) 코드이기 때문에 90%이상의 runtime을 얻을 수 있었다고 본다.

사실 Accept가 떨어진 순간부터는 답은 맞았다고 봐야하지만.. 조금 개선 된 코드를 만들어보는건 항상 필요할 것이다.