[백준] 1334번: 다음 팰린드롬 수

https://www.acmicpc.net/problem/1334

initial

def make_it_palin(num):
    num = str(num)
    if all(char == '9' for char in num):
        return '1' + '0' * (len(num) - 1) + '1'
    if num[:len(num)//2+1] == num[len(num)//2:]:
        return num
    if len(num) == 1:
        return str(int(num) + 1)

    num = int(num)
    num += 1
    return str(num)

def check_and_return_palin(left, right, mid, flag):
    if int(right) <= int(left[::-1]):
        return left + mid + left[::-1]
    else:
        if flag:
            mid = int(mid)
            mid += 1
            mid = str(mid)
        return left + mid + left[::-1]

string = input()
n = int(string)

if n < 9:
    print(n + 1)
    exit()
elif n == 9:
    print(11)
    exit()
else:
    length = len(string)
    if length % 2 == 0:
        left, right = string[:length//2 - 1], string[length//2 + 1:]
        mid = make_it_palin(string[length//2 - 1:length//2 + 1])
        if all(char == '0' for char in mid):
            left = str(int(left) + 1)
        print(check_and_return_palin(left, right, mid, False))
    else:
        left, right = string[:length//2], string[length//2 + 1:]
        mid = make_it_palin(string[length//2])
        if all(char == '9' for char in mid):
            left = str(int(left) + 1)
        print(check_and_return_palin(left, right, mid, True))

So my logic was kinda wrong in that i tried making changes to the mid value for strings that have even lengths. (well i think you can somehow impl it its not wrong). But ive seen an easier pattern solution where for even strings, if the reversed left subtring has larger value than right substring, we can just take the left substring and append it to the right of our left substring.

https://anwltjdzheldsbql.tistory.com/42 refer to this.

Also I struggled a lot with a case when string length is odd. When

elif len(up_left)>len(left):           

the logic is different when it has even or odd lengths. For example for even length like 9999, we dont wanna do "100" + "001", which gives us 100001 cuz the correct answer should be 10001. So notice the 0 has been removed. So we slice the first character of the reversed left substring.

But for odd length like 999, left substring +1 is 10. So we can just do "10" + "01" which gives "1001.

ALSO RMB to strip the string input cuz you dont want the newline character (\n) to be included in your string.

solution

Overall i feel it is a brute force impl.

import math

string = input().strip()
n = int(string)

if n < 9:
    print(n + 1)
    exit()
elif n == 9:
    print(11)
    exit()
else:
    length = len(string)
    if length % 2 == 0:
        left, right = string[:length // 2], string[length // 2:]
        if int(right) < int(left[::-1]):
            print(left + left[::-1])
        else:
            up_left = str(int(left) + 1)
            if len(up_left) == len(left):
                print(up_left + up_left[::-1])
            elif len(up_left)>len(left):
                print(up_left + up_left[::-1][1:])
    else:
        left, right = string[:length // 2], string[length // 2 + 1:]
        mid = string[length // 2]
        if int(right) < int(left[::-1]):
            print(left + mid + left[::-1])
        else:
            if int(mid) == 9:
                up_left = str(int(left) + 1)
                if len(up_left) == len(left):
                    print(up_left + "0" + up_left[::-1])
                elif len(up_left)>len(left):
                    print(up_left + up_left[::-1])
            else:
                print(left + str(int(mid) + 1) + left[::-1])

dp way

there is actually a dp way tbc

complexity

Let's analyze the time and space complexity of your code:

Time Complexity:

• The time complexity of the code is primarily determined by the operations inside the if-else conditions. The operations involve string manipulations, conversions, and comparisons.
• The maximum time complexity is determined by the length of the input string, which is denoted as 'length'.
• The string manipulations and conversions are generally linear in terms of the length of the string, so the overall time complexity is O(length).

Space Complexity:

• The space complexity of the code is also influenced by the length of the input string.
• The additional space used is mainly for the variables left, right, up_left, and mid, which store substrings or converted values. The space required for these variables is proportional to the length of the input string.
• Therefore, the overall space complexity is O(length).

In summary, both the time and space complexity of the code are linear, O(length), where 'length' is the length of the input string.