Post

[LeetCode] #9 - Palindrome Number [Java][C++][Python]

[LeetCode] #9 - Palindrome Number [Java][C++][Python]

문제 링크


1. 아이디어

정수가 회문인지, 즉 문자열로 바꿨을 때 앞뒤로 똑같이 읽히는지 보는 문제로, 문자열을 뒤집어 원래와 같은지 비교하면 된다.

지문의 Follow-up은 문자열로 바꾸지 않고 푸는 것을 묻고, 절반 뒤집기가 그것에 맞춘 풀이이다. 수 전체를 뒤집으면 2,147,483,647이 7,463,847,412가 되듯 뒤집은 값이 32비트 범위를 넘을 수 있어서 뒤 절반만 뒤집는다. 낮은 자리를 하나씩 떼어 뒤집은 수에 붙이는 일을 뒤집은 수가 남은 수 이상이 될 때까지 되풀이하는데, 회문이면 이때 남은 수가 앞 절반이고 뒤집은 수가 뒤 절반이라 둘이 같고(자릿수가 홀수이면 가운데 자리가 뒤집은 수 쪽에 들어가므로 뒤집은 수를 10으로 나눈 몫과 같다), 회문이 아니면 어디서 멈추든 둘이 같지 않다.

음수는 - 때문에, 끝자리가 0인 수(0은 제외)는 앞자리가 0일 수 없어서 회문이 될 수 없으므로 처음에 거짓으로 처리한다. 끝자리 0을 거르지 않으면 입력 10에서 반복이 끝난 뒤 남은 수 0과 뒤집은 수 1을 10으로 나눈 몫 0이 같아져 참이 되어 버린다.


2. 코드

풀이 1: 문자열 변환 [Java][C++][Python]

1
2
3
4
5
6
class Solution {
    public boolean isPalindrome(int x) {
        String s = String.valueOf(x);
        return s.equals(new StringBuilder(s).reverse().toString());
    }
}
1
2
3
4
5
6
7
8
9
10
#include <bits/stdc++.h>
using namespace std;

class Solution {
   public:
    bool isPalindrome(int x) {
        string s = to_string(x);
        return s == string(s.rbegin(), s.rend());
    }
};
1
2
3
4
class Solution:
    def isPalindrome(self, x: int) -> bool:
        s = str(x)
        return s == s[::-1]

풀이 2: 절반 뒤집기 [Java][C++][Python]

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean 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 x == rev || x == rev / 10;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;

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 x == rev || x == rev / 10;
    }
};
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0 or (x != 0 and x % 10 == 0):
            return False

        rev = 0
        while x > rev:
            rev = rev * 10 + x % 10
            x //= 10

        return x == rev or x == rev // 10

This post is licensed under CC BY 4.0 by the author.