Quiz) 주어진 값 다음으로 큰 회문을 찾아보자

Problem

Given a number, find the next smallest palindrome larger than this number. For example, if the input number is “2 3 5 4 5”, the output should be “2 3 6 3 2”. And if the input number is “9 9 9”, the output should be “1 0 0 1”.
The input is assumed to be an array. Every entry in array represents a digit in input number. Let the array be ‘num[]’ and size of array be ‘n’

Example

There can be three different types of inputs that need to be handled separately. 
1) The input number is palindrome and has all 9s. For example “9 9 9”. Output should be “1 0 0 1” 
2) The input number is not palindrome. For example “1 2 3 4”. Output should be “1 3 3 1” 
3) The input number is palindrome and doesn’t have all 9s. For example “1 2 2 1”. Output should be “1 3 3 1”.

Approach

회문이란 중간에 거울을 둔 것처럼 앞으로 읽으나 뒤로 읽으나 같은 글을 의미합니다.
우리가 장난삼아 하던 말들, "기러기는 거꾸로 읽어도 기러기"과 같은 단어가 회문이죠. ㅎㅎ

위에 제시된 문제에서는 숫자로 이루어진 회문을 찾아보라고 이야기합니다. 떠오르는 심플한 방법은 이거죠. 주어진 값을 "1"씩 증가시켜가며 증가된 값이 회문이 되는지 확인해보면 됩니다. 하지만 이렇게 한다면 시간 복잡도가 어마어마하게 늘어나게 되겠죠.

알고리즘 시험에서 위와 같은 문제는 시간 복잡도 제약이 함께 주어지기 때문에, 다소 복잡하더라도 규칙성을 찾아내어 처리해주는 것이 좋습니다.

이제 우리는 위 문제를 풀기 위하여 두 가지를 먼저 알아보고자 합니다.

1. 회문인지 어떻게 알 수 있을까? 어떻게 만들 수 있을까?
2. 주어진 값 다음으로 큰 회문은 어떻게 구할까?

하나씩 차근차근 보도록 하겠습니다.

1. 회문인지 어떻게 알 수 있을까?

우선 숫자를 자릿수 별로 하나씩 띄어서 써보고 중간 위치를 찾아봅니다. 그리고 여기에 거울이 있다고 생각하면 회문 판별 및 새로운 회문 생성이 쉬워집니다.

아래 박스에서 두 가지 예를 들어보도록 하겠습니다.

`[ ]` 기호를 통해 거울을 표현하였습니다.

# 짝수자릿수 숫자
"1 2 3 4 5 6" ===> "1 2 3 [] 4 5 6"

# 왼쪽을 비추는 경우
"1 2 3 3 2 1"

# 오른쪽을 비추는 경우
"6 5 4 4 5 6"

위에서 처럼 자릿수가 짝수개인 수는 임의의 빈 공간에 거울이 생성됩니다. 그리고 한쪽을 거울을 통해 비추게 되면 회문이 생성되게 됩니다.

`[ ]` 기호를 통해 거울을 표현하였습니다.

# 홀수자릿수 숫자
"1 2 3 4 5" ===> "1 2 [3] 4 5"

# 왼쪽을 비추는 경우
"1 2 3 2 1"

# 오른쪽을 비추는 경우
"5 4 3 4 5"

마찬가지로 홀수 자릿수를 가진 숫자도 거울을 통해 왼쪽 오른쪽을 비춤으로써 회문을 만들 수 있습니다. 단, 거울의 위치는 빈 공간이 아니고 특정 숫자에 위치하게 됩니다.

위에서 보여 주듯이 우리는 거울의 위치를 통해 도출되는 왼쪽, 오른쪽의 첫 번째 인덱스 값을 알 수 있습니다. 그리고 이 위치 값들을 통해 회문의 생성, 판별이 가능하게 됩니다.

# 짝수 자릿수의 위치

number	1	2	3	4	5	6
index	0	1	2	3	4	5
position			Left	Right

# 홀수 자릿수의 위치

number	1	2	3	4	5
index	0	1	2	3	4
position		Left		Right

2. 주어진 값 다음으로 큰 회문은 어떻게 구할까?

그렇다면 어떤게 주어진 값 다음으로 큰 회문일까요? 회문이 아닌 일반적인 경우, 우리는 보통 낮은 자릿수의 값을 증가시킴으로 주어진 값의 다음으로 큰 수를 찾게 됩니다. 하지만 회문의 경우 가장 낮은 자리 숫자를 증가시킨 다는 것은 가장 높은 자릿수를 함께 증가시킨다는 것과 일맥상통하게 됩니다.

예를 들어 "1 2 3 2 1"이라는 회문의 가장 마지막 자릿수인 "1"을 증가시키고자 하면 다음과 같이 되게 됩니다.

"1 2 3 2 1" ===> "2 2 3 2 2"

가장 높은 자릿수도 함께 움직이게 되는 거죠. 이 값은 회문이지만, 주어진 값의 바로 다음 회문이라는 보장은 할 수 없습니다.

이렇기 때문에 우리는 다음 회문을 찾을 때, 낮은 자리가 아닌 중간 자리부터 값을 증가시켜가야 합니다.

"1 2 3 2 1" ===> "1 2 4 2 1"

위처럼, 중간 값 '3'을 증가시킨 값이 회문이 됩니다. 하지만 만약 가운데 값이 '9'라면 어떻게 될까요? 마찬가지로 중간 값을 증가시키되, 10을 넘어가는 수가 생기면 양 옆으로 전파(캐리)를 해야 합니다.

Example. "1 2 9 2 1"
---------------------
Step 1. 중간 값 증가 ===> "1 2 10 2 1"
Step 2. 캐리 전파 ===> "1 2(+1) 0 2(+1) 1"
Step 3. 정리 ===> "1 3 0 3 1"

우리는 위 방법을 반복함으로써 주어진 값 보다 큰 회문을 찾을 수 있습니다.

Solution (Python)

이번에는 파이썬으로 풀이를 진행해보았습니다. 코드에서도 최대한 위 내용을 풀어서 표현하려고 노력해보았습니다.
코드를 간결하게 하기 위하여 모든 수가 "9"로 이루어진 입력 값에 대하여는 따로 처리하도록 구성하였습니다.
(위와 같은 경우는 최종 자릿수가 증가하기 때문에 별도로 처리하였습니다.)

import copy


class Palindrome:
    def __init__(self, numbers: []):
        self.numbers = numbers
        self.mid = int(len(numbers) / 2)

    def makePalindrome(self):
        palindrome = copy.deepcopy(self.numbers)

        i = self.mid - 1
        j = self.mid + 1 if len(self.numbers) % 2 == 1 else self.mid
        while i >= 0 and palindrome[i] == palindrome[j]:
            i -= 1
            j += 1

        while i >= 0:
            palindrome[j] = palindrome[i]
            i -= 1
            j += 1

        return palindrome

    def compare(self, palindrome):
        a = int(''.join(map(str, self.numbers)))
        b = int(''.join(map(str, palindrome)))

        return a < b

    def findNext(self, palindrome):
        carry = 1
        left = self.mid - 1 if self.mid != 0 else self.mid
        right = self.mid + 1 if len(self.numbers) % 2 == 1 else self.mid

        if len(palindrome) % 2 == 1:
            palindrome[self.mid] += carry
            carry = int(palindrome[self.mid] / 10)
            palindrome[self.mid] %= 10

        while left >= 0 and carry != 0:
            palindrome[left] += carry
            carry = int(palindrome[left] / 10)
            palindrome[left] %= 10
            palindrome[right] = palindrome[left]
            left -= 1
            right += 1

        return palindrome

    def nextPalindrome(self):
        if self.areAll9s():
            return self.newPalindromeForAll9s()

        palindrome = self.makePalindrome()

        while not self.compare(palindrome):
            palindrome = self.findNext(palindrome)

        return palindrome

    def display(self, outputs):
        for num in outputs:
            print(num, end=" ")

    def areAll9s(self):
        for number in self.numbers:
            if number != 9:
                return False
        return True

    def newPalindromeForAll9s(self):
        palindrome = [1]
        for i in range(1, len(self.numbers)):
            palindrome.append(0)
        palindrome.append(1)

        return palindrome


if __name__ == "__main__":
    # inputs = [9, 4, 1, 8, 7, 9, 7, 8, 3, 2, 2]
    # inputs = [1, 2, 3, 4, 5, 6]
    # inputs = [1, 9, 1]
    inputs = [1, 2, 9, 2, 1]
    # inputs = [9, 9, 9]
    maker = Palindrome(inputs)
    outputs = maker.nextPalindrome()
    maker.display(outputs)

위 코드는 O(n)의 시간 복잡도를 가지게 될 것으로 보입니다.

Review

코드를 작성하고 정리할까 고민을 했는데, 결국 귀찮아서 테스트하던 날 것 그대로 올리게 되었습니다.
개인적으로 이번 `Approach`를 좀 더 잘 써보고 싶었습니다만, 역시나 귀찮아서 이 정도 선에서 마무리된 것 같습니다.
원래는 그림도 직접 그려서 올리고 하려했는데.. 텍스트 박스로 대충 때우게 되었습니다.
다음엔 좀 더 부지런하게, 퀄리티 높은 포스팅을 해볼 수 있으면 좋겠습니다.

Reference

https://www.geeksforgeeks.org/given-a-number-find-next-smallest-palindrome-larger-than-this-number/

Given a number, find the next smallest palindrome - GeeksforGeeks