[Python] BOJ(백준) 1334 다음 펠린드롬 수

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

 

문자열 구현 문제다.

 

펠린드롬 수라고 해서 1씩 키워서 펠린드롬인지 확인해봐야지 라고 생각했으나 자릿수가 최대 50인 걸 보고 바로 문자열로 틀었다.

이전에는 문자열에서 1씩 키워서 확인하는 방법을 사용했던 것 같다. (당연히 시간초과겠지^^)

 

3년 만에 문제를 다시 보고 바로 든 생각은 중점을 기준으로 비교해나가는 것이었다.

해당 수 보다 크면서 가장 작은 펠린드롬 수를 구하기 위해서는 최대한 뒤쪽 수를 높여야 한다.

 

중점 기준으로 중앙에서부터 왼쪽과 오른쪽 문자를 비교해나간다.

왼쪽 문자가 큰 경우 오른쪽 문자만 값을 키우면 되고, 오른쪽 문자가 큰 경우 중점 값을 키우면 된다.

 

처음에는 문자열 길이가 짝수인 경우와 홀수인 경우를 나눠서 생각하고 코드를 짰다.

사실상 중점이 하나냐, 두개냐의 차이만 있을 뿐 코드는 동일하기 때문에 추후에 코드를 합쳤다.

생각하기 어렵다면 두개를 분리해서 생각하는 것도 방법!

 

1 2 3 4 5

인 경우 3을 기준으로 2와 4를 비교 했을 때, 4(오른쪽)가 더 크므로 3 -> 4로 중점에 1을 더한다.

그 후 왼쪽의 반쪽을 뒤집어 뒤에 이어주면 된다 1 2 + 4 + 2 1

 

1 2 3 4

인 경우 2 3을 기준으로 3(오른쪽)이 더 크므로 2 -> 3 을 하면 된다.

문자열의 길이가 짝수인 경우 중점 두 개 중 왼쪽 값 1만 올려주면 오른쪽 값은 어떤 수가 와도 기존 수보다 커진다.

펠린드롬 조건만 만족하면 되므로 홀수와 마찬가지로 왼쪽 반을 뒤집어 오른쪽을 구성하면 된다.

 

1 4 3 2 5

인 경우 3을 기준으로 4(왼쪽)이 더 크므로 별다른 처리 없이 왼쪽을 뒤집어주면 된다.

 

1 4 3 2

의 경우도 마찬가지다.

 

일반적인 숫자들에 대해서는 이 부분만 파악하면 문제가 되지 않는다.

 

일반적인 경우 외에 특별한 예외에 대해서 몇가지 고려를 해야한다.

 

1. 자릿수가 늘어나는 경우

이 경우는 들어온 값이 9로만 이루어진 경우 밖에 없다. 어떤 수가 들어오든 그 자릿수 안에서 해결된다.

998 997 996 995 등 다 999로 만들어지기 때문이다.

그래서 이 경우만 별도로 예외처리를 해주었다.

9로만 이루어진 경우에는 100---001 이 출력되도록 했다.

 

2. 입력된 수가 펠린드롬 수인 경우

입력된 수 보다 큰 수여야 하기 때문에 입력된 수는 제외해야 한다.

처음에는 만들어진 펠린드롬 수가 원래와 같은 경우 중앙 수를 1 올려준다.

펠린드롬의 반쪽 수를 어떻게 한다~ 등등 생각했었다.

 

그러나 입력된 수가 펠린드롬이라면 초기에 입력값 + 1을 한 후에 똑같은 절차를 거치도록 했다.

 

3. 1을 더할 때 9인 경우

일반적인 경우에서 어딘가에 1을 더해주는 경우가 생기게 되는데, 이 때 9인 경우를 조심해야 한다.

그냥 1을 더해버리면 10이 되면서 자릿수가 늘어나게 되는 마법이 펼쳐진다.

그 부분은 while 문을 사용해 올림 연산을 따로 해주었다.

 

+) 추가적으로 어차피 왼쪽 값을 뒤집어서 최종 펠린드롬 수를 만들 것이기 때문에 항상 값은 왼쪽만 변경하였다.

 

import sys
input = sys.stdin.readline

n = input().rstrip('\n')
n = list(n)
l = len(n)

if n == ['9'] * l:
    print('1' + '0' * (l - 1) + '1')

else:
    if n[:] == n[:][::-1]:
        k = l - 1
        while(n[k] == '9'):
            n[k] = '0'
            k -= 1
        n[k] = str(int(n[k]) + 1)
        
    if l % 2 == 0:
        left = l // 2 - 1
        right = l // 2
    else:
        left = right = l // 2
        
    for i in range(right + 1):
        if n[left - i] > n[right + i]:
            break
        elif n[left - i] < n[right + i]:
            k = left
            while n[k] == '9':
                n[k] = '0'
                k -= 1
            n[k] = str(int(n[k]) + 1)
            break
            
    n = ''.join(n)
    if l % 2 == 0:
        print(n[:l//2] + n[:l//2][::-1])
    else:
        print(n[:l//2] + n[l//2] + n[:l//2][::-1])

 

코드를 넣을 때마다 시작도 전에 틀렸습니다가 계속 나왔다.

반례들을 넣어봐도 다 맞는데 아찔했다...

그러다가 생각난 게 저번에도 이래서 해결했던 경험이 떠올랐고, 마침 이번에도 문자열 입력을 받는 것이었다.

그래서 입력 뒤에 .rstrip('\n')을 붙여줬더니 바로 성공.

 

문자열 한 줄 입력 받는 건 문제가 없을 줄 알았다...

문자열과 rstrip은 세트... 메모... 📝