Palindrome Number

Q: 음수도 회문인가요?

아니요. 거꾸로 읽으면 -121 은 121- 이 되고, 마이너스 기호의 반대쪽 끝에는 짝이 되는 문자가 없습니다. 따라서 모든 음의 정수는 false 를 반환합니다.

Q: 왜 숫자의 절반만 뒤집나요?

모든 숫자를 뒤집으면 32비트 정수에서 오버플로가 발생할 수 있습니다. 2147483647 을 뒤집은 값은 가장 큰 int 보다 큽니다. 숫자의 절반은 항상 들어가므로, 루프는 작업의 절반만 수행합니다.

Q: Palindrome Number의 시간 복잡도는 얼마인가요?

두 접근 방식 모두 O(log x) 시간에 실행됩니다. 숫자 x 에는 약 log10(x) 개의 자릿수가 있고 각 자릿수를 한 번씩 처리하기 때문입니다. 문자열 접근 방식은 텍스트를 위해 O(log x) 의 추가 공간을 사용하고, 절반 뒤집기 방식은 O(1) 을 사용합니다.

쉬움수학과 시뮬레이션

+10

숫자의 자릿수를 왼쪽에서 오른쪽으로 읽을 때와 오른쪽에서 왼쪽으로 읽을 때 같은 숫자를 회문이라고 합니다. 예를 들어 1221이 있습니다. 정수 x가 주어졌을 때, 회문이면 true를 반환하고 그렇지 않으면 false를 반환하세요. 음수는 절대 회문으로 간주되지 않습니다. 음수 기호의 반대편 끝에는 짝이 되는 기호가 없기 때문입니다.

함수

isPalindrome(x: integer) → boolean

xinteger: 검사할 정수(음수일 수도 있음)
반환값boolean: x를 양방향으로 읽었을 때 동일하면 true, 그렇지 않으면 false

제약 조건

-2³¹ ≤ x ≤ 2³¹-1
모든 음수는 false를 반환합니다.

예제

입력: x = 121
출력: true
설명: 거꾸로 읽어도 121은 여전히 121이므로 답은 true입니다.

입력: x = -121
출력: false
설명: 거꾸로 읽으면 -121은 121-이 되는데, 이는 다른 텍스트이므로 답은 false입니다.

후속 질문

정수를 문자열로 변환하지 않고 풀 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

숫자는 자기 자신을 뒤집은 값과 같으면 회문입니다. 텍스트로 다루면 한 번의 비교로 확인할 수 있습니다. 텍스트를 사용하지 않으면 뒤집은 숫자 전체를 다시 만들 때 오버플로가 발생할 수 있으므로, 숫자의 뒷부분만 뒤집어 앞부분과 비교하세요.

문자열과 그 역순을 비교합니다

핵심 아이디어

숫자를 텍스트로 쓰고 뒤집은 텍스트와 비교합니다. 음수는 특별히 처리할 필요가 없습니다. -121은 마이너스 기호로 시작하고 숫자로 끝나므로, 뒤집은 텍스트인 121-와 절대 같지 않습니다.

텍스트에는 각 자릿수마다 문자 하나가 있으므로, 문자는 약 log10(x)개이며 여기서는 최대 11개입니다. 추가 문자열이 비용입니다.

알고리즘

x를 문자열 s로 변환합니다.
s를 뒤집습니다.
s가 뒤집은 결과와 같은지 반환합니다.

def isPalindrome(x):
    s = str(x)
    # A minus sign sits only at the front, so a negative never matches its reverse.
    return s == s[::-1]

숫자의 절반을 거꾸로

핵심 아이디어

x % 10은 마지막 자릿수를 반환하고, 10으로 정수 나눗셈을 하면 그 자릿수가 제거됩니다. x의 끝에서 자릿수를 가져와 두 번째 숫자 half에 붙이면 제거한 자릿수의 역순이 만들어집니다. half가 남은 x보다 크거나 같아지면 멈춥니다. 자릿수의 절반을 가져온 상태입니다. 1221은 x = 12와 half = 12로 끝나므로 회문입니다. 자릿수 개수가 홀수이면 half에는 가운데 자릿수도 포함됩니다. 12321은 x = 12와 half = 123으로 끝나므로 x와 half / 10을 비교합니다.

반복문을 시작하기 전에 두 가지 경우를 처리합니다. 음수는 회문이 될 수 없습니다. 0으로 끝나는 숫자는 0으로 시작해야 하는데, 이는 0뿐입니다. 이 검사가 없으면 10은 x = 0과 half = 1로 끝나고, x == half / 10이 잘못 통과합니다. half는 6자릿수를 넘지 않으므로 어떤 정수형에도 들어갑니다.

알고리즘

x가 음수이거나 0이 아니면서 0으로 끝나면 false를 반환합니다.
half = 0으로 설정합니다.
x > half인 동안 half = half * 10 + x % 10으로 설정하고, 정수 나눗셈으로 x를 10으로 나눕니다.
x == half(자릿수가 짝수인 경우) 또는 x == half / 10(자릿수가 홀수인 경우)이면 true를 반환합니다.

def isPalindrome(x):
    if x < 0:
        return False
    original, reversed_num = x, 0
    while x > 0:
        reversed_num = reversed_num * 10 + x % 10
        x //= 10
    return original == reversed_num

함정과 경계 사례

음수를 고려하지 않는 경우. 나머지가 부호를 유지하는 언어에서는 -121을 뒤집어도 -121이 되어 검사가 통과합니다. -1 // 10이 -1인 Python에서는 while x != 0 루프가 끝나지 않습니다.
0으로 끝나는 숫자를 거부하지 않는 경우. 그러면 절반만 뒤집는 방법이 10을 받아들입니다. 0 자체는 회문입니다.
32비트 정수에서 숫자 전체를 뒤집는 경우. 2147483647을 뒤집은 값은 범위에 들어가지 않습니다.
언어가 분수로 나누는 경우 /를 사용하는 것. JavaScript에서는 Math.floor(x / 10), Python에서는 //, R에서는 %/%, Dart에서는 ~/를 사용하세요.
루프가 x를 변경한 뒤 전체 역수를 x와 비교하는 경우. 원래 값의 복사본을 보관하세요.

자주 묻는 질문3

음수도 회문인가요?

아니요. 거꾸로 읽으면 -121은 121-이 되고, 마이너스 기호의 반대쪽 끝에는 짝이 되는 문자가 없습니다. 따라서 모든 음의 정수는 false를 반환합니다.

왜 숫자의 절반만 뒤집나요?

모든 숫자를 뒤집으면 32비트 정수에서 오버플로가 발생할 수 있습니다. 2147483647을 뒤집은 값은 가장 큰 int보다 큽니다. 숫자의 절반은 항상 들어가므로, 루프는 작업의 절반만 수행합니다.

Palindrome Number의 시간 복잡도는 얼마인가요?

두 접근 방식 모두 O(log x) 시간에 실행됩니다. 숫자 x에는 약 log10(x)개의 자릿수가 있고 각 자릿수를 한 번씩 처리하기 때문입니다. 문자열 접근 방식은 텍스트를 위해 O(log x)의 추가 공간을 사용하고, 절반 뒤집기 방식은 O(1)을 사용합니다.

def isPalindrome(x):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

인자

x = 121

예상 출력

true