문제 링크: https://www.acmicpc.net/problem/4096

Thumbnail: Photo by Spencer Backman (Unsplash)

생각만큼 간단하지 않아서 몇차례 고전했습니다...

생각한 과정

문자열을 \(S\), 이 문자열의 길이를 \(L\)이라고 합시다.
먼저 주어진 숫자가 팰린드로미터가 맞는지 판단하기 위해 1차례 문자열의 절반 (\(L\))만큼 반복하며 양 끝을 비교합니다.
이후, 팰린드로미터가 아니라면 다시 문자열의 절반 (\(L\))만큼 반복하며 양 끝을 비교하고, 앞쪽 (높은 자릿수)의 수를 기준으로 뒷쪽 (낮은 자릿수)의 수에 일정 수를 더해 두 수를 같게 맞춥니다. 자리올림은 다음 자리의 계산에 고려합니다.

그러나... 이 방식대로면 자리올림이 앞쪽 절반까지 넘어갈 경우 계산하지 못합니다.
그래서 더해야 할 수를 찾는 과정을 문자열 전체만큼 반복하도록 했더니, 오히려 결과값이 과도하게 커지는 현상이 발생했습니다.

고민하다 그냥 단순한 방법으로 부딪혔습니다. 1씩 더하며 회문인지 판단하는 방식으로... 문제 조건에서 주어지는 수가 2자리~9자리라고 하였고, 실제로 회문을 만들기 위해 더해야 하는 수는 그 수의 절반 정도일 것이라 예상했기에 실제로는 1개 숫자 마다 최대 \(10 \ times 5\)정도 반복하지 않을까? 라고 예측했고, 문제 조건이 여유가 있어서 그런가 일단 정답은 되었습니다만... 이렇게 1씩 더하는 방법보다 더 나은 방법은 없을지 여전히 고민입니다.

풀이

회문인지 검사하는 함수 is_palindrome을 정의합니다. 이 함수는 전체 배열의 길이의 절반만큼 반복하며, 양 끝 값을 비교하며 회문인지 판단해 bool 값으로 결과를 반환합니다.

def is_palindrome(x):
    for i in range(len(x) // 2):
        if x[i] != x[-(i + 1)]:
            return False
    return True

이후, 수를 입력받아 각 자리에 해당하는 정수 값을 가진 list로 바꾸고, 먼저 is_palindrome을 1회 수행해 회문인지 판단합니다. 회문이라면 0을 출력하고 다음 수로 넘어갑니다.

만약 회문이 아닌 경우에는, 계속 1씩 더하며 회문이 되는지 비교합니다. 이때, 배열 형태로 값을 유지하며 자리올림을 처리해줍니다.

전체 코드

from sys import stdin

def is_palindrome(x):
    for i in range(len(x) // 2):
        if x[i] != x[-(i + 1)]:
            return False
    return True

while True:
    x_list = list(map(int, stdin.readline().rstrip()))
    if len(x_list) == 1: # 종료 조건 (사실 0 제외하면 5자리 이상인데 그냥 자리수만 세도 맞지 않을까?)
        break
    
    if is_palindrome(x_list):
        print(0)
    else:
        result = 0
        while not is_palindrome(x_list):
            result += 1
            x_list[-1] += 1
            for i in range(len(x_list)-1, 0, -1):   # 자리 올림 처리
                if x_list[i] == 10:
                    x_list[i] = 0
                    x_list[i-1] += 1
        print(result)

개선할 수 있는 부분?

최초 아이디어에서 사용했던 '대칭이 되는 자릿수 간의 숫자 비교'를 사용하면, 굳이 1씩 더하지 않고도 각 자리를 맞출 수 있지 않을까 싶습니다. 좀 더 고민해봐야겠습니다..