WN_인생기록

LeetCode - 9. Palindrome Number 본문

LeetCode/Easy

LeetCode - 9. Palindrome Number

WhNi 2024. 3. 27. 14:17

팰린드룸(회문) 에 대한 문제이다.

 

int 형으로 된 숫자가 회문인지 아닌지 판단하는 알고리즘을 구하는 문제이다.

 

예시에는 기본 상태와, 예외 처리해야할 예시들이 보여진다. 

(음수는 팰린드룸 X, 10 일때는 01 이기 때문에 회문이 될 수 없음)

 

정리하자면 

 

앞부분과 뒷부분이 같아야 하는데, 음수이면 안되고, 10의 배수이거나 0이여서도 안됨

 

class Solution {
public:
    bool isPalindrome(int x) 
    {
         // 음수 제외, 10의 배수 제외, 0 제외 조건
        if (x < 0 || (x % 10 == 0 && x != 0))
            return false;
            
		// x 값을 original에 복사
        original = x;
        
        // 자릿값 구하기
        while (x > 0)
        {
            length++;
            x /= 10;
        }
        
        // 자릿수를 통해서 앞자리 구하기 
        front = original / (pow(10,(length / 2)));
        
        // original의 %(나머지 연산)을 통해서 뒷자리 구하기
        while (original > reverse)
        {
            reverse = reverse * 10 + original % 10;
            original /= 10;
        }
        
        // 앞자리 뒷자리 비교하기
        if (front == reverse)
        {
            return true;
        }
        return false;
    }
private:
    int front;
    int reverse;
    int original;
    int length;
};

 

처음에는 이런식으로 클래스와 멤버 변수들을 활용해서 작성해봤는데, 생각보니까 불필요한 것들이 많은거 같았다. 

 

멤버 변수에 대한 정의가 너무 많아서 굳이 이렇게 안해될텐데 싶었다. 물론 이렇게 해서 문제는 풀리지만 좀 더 효율적으로 만들고 싶었다. 메모리 사용도 너무 많아서, 줄이고 싶었다.

class Solution {
public:
    bool isPalindrome(int x) 
    {
         // 음수 제외, 10의 배수 제외, 0 제외 조건
        if (x < 0 || (x % 10 == 0 && x != 0))
            return false;
        
        // 멤버 변수 아닌, 일반 변수로 선언 + log를 활용함으로써 자릿수 파악하기
        // 자릿수/2 값으로 팰린드룸 기준 정해서 앞자리 구하기
        int front = x /pow(10,(int)log10(x)/2);
        
        // 뒷자리 초기화 한 뒤, 뒷자리 구하기
        int reverse =0;
        while(x > reverse)
        {
        	reverse = reverse * 10 + x % 10;
        	x /= 10;
        }
        
        return (front == reverse) ? true : false; 
    }

};

 

이렇게 줄였더니 문제가 발생했다. 바로 (int)log10(x/2) 부분에서 회문 기준으로 정확하게 나누지 못할때가 발생한다.

즉 홀수 자릿수 일때 오답이 나온다. 그래서 이부분을 갈아엎고 새로운 방식으로 접근했다.

 

class Solution {
public:
    bool isPalindrome(int x) {
        // 음수와 10의 배수(0 제외)는 팰린드롬이 아님
         if (x < 0 || (x % 10 == 0 && x != 0))
         {
            return false;
         }

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

        // x와 reverse가 같거나, 홀수 자릿수일 경우 중앙 숫자를 제외하고
        //x가 reverse/10과 같은지 확인
        
        return x == reverse || x == reverse / 10;
    }
};

앞자리를 따로 구하는게 아니라, 뒷자리 구할때 동시에 같은 지점에서 멈출 수 있도록 한뒤, 비교할때 홀수라면 x가 한자릿수 모자를테니, /10 을 해줌으로써 중앙값을 빼주는 역할을 한다. 그러면 회문인지 아닌지 판단이 바로 가능함으로, 많은 과정을 줄인셈이다. 

 

이렇게 코드가 간결하게 마무리 되었다. 

 

 

별거 아닌 알고리즘이지만, 다양한 방법으로 시간 복잡도와 공간 복잡도에 대한 비교를 할 수 있어서

 

더 효율적인게 뭔지 어렴풋이 파악이 가능했다.

'LeetCode > Easy' 카테고리의 다른 글

LeetCode - 14.Longest Common Prefix  (0) 2024.03.27
LeetCode - 13 Roman to Integer  (0) 2024.03.27