[ Baekjoon - 11/02 ] - 1334번: 다음 팰린드롬 수

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

1334번: 다음 팰린드롬 수

 

• 소요 시간 : 2시간 반 (자바 자료형 고민하다가 시간을 좀 많이 날렸다..)

다음 팰린드롬 수 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

3174

485

359

20.271%

문제

팰린드롬 수는 앞으로 읽어도, 뒤로 읽어도 같은 숫자이다. 101, 4, 6666와 같은 숫자는 팰린드롬 수이고, 10, 564, 15452와 같은 숫자는 아니다.

어떤 수 N이 주어질 때, N보다 큰 팰린드롬 수 중에서 가장 작은 수를 출력한다.

입력

첫째 줄에 N이 주어진다. N은 최대 50자리인 양의 정수이다. 첫 숫자는 0이 아니다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력 1 복사

12345

예제 출력 1 복사

12421

예제 입력 2 복사

858

예제 출력 2 복사

868

예제 입력 3 복사

1999

예제 출력 3 복사

2002

예제 입력 4 복사

1

예제 출력 4 복사

2

예제 입력 5 복사

9999

예제 출력 5 복사

10001

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 2초
     • 메모리 : 128MB
   • 문제
     
     • 숫자 N(N은 최대 50자리인 양의정수)
     • 숫자 N보다 크되, 가장 작은 팰린드롬수를 출력하는 문제
   • 이해
     • 팰린드롬관련 문제는 푼적이 있어서 이해는 어렵지 않았다.
2. 문제를 익숙한 용어로 재정의와 추상화
   • 생략
3. 문제를 어떻게 해결할 것인가
   • 저번 펠린드롬 문제는 dp로 풀었어서 이번에도 그런 접근을 해야할지 생각해보았는데, 여러 값이 아닌 단 하나의 값만 도출하면 되므로, dp보다는 단순히 가까운수 찾는 문제라고 생각되어 다른 방법을 시도하기로 했다.
   • 1st 접근 - 펠린드롬의 정의를 이용한 단순한 방식 )
     • N보다 크면서 가장 가까운 펠린드롬을 찾는 것이기때문에, 가장 단순하게 생각하면 N을 1씩더해가며 펠린드롬인지 확인하는 방법이 있다.
     • 펠린드롬은 중간을 기준으로 앞뒤를 비교했을때 같으면 펠린드롬이기 때문에 글자를 뒤집어야하는데, 50글자이상인 N이므로 뒤집는 연산이 꽤 크기 때문에 이 방법은 시간초과를 일으킬 것같아서 패스.
   • 2nd 접근 - 상황에 따른 조건 분기점으로 구하는 방식 )
     • 우선 반을나눠 비교하는 연산을 해야한다는것은 필수적이므로, 홀짝의 경우, 앞의수와 뒤의수의 차이로 판단해야한다 생각했다.
     • 앞의 자리수가 뒷자리수를 뒤집은값보다 작다면, 중간값에 1을 더하고 뒷자리는 앞의자리수를 뒤집은값으로,
       앞의 자리수가 뒷자리수를 뒤집은값보다 크다면, 뒷자리수를 앞자리수를 뒤집은값으로 넣으면 되었다!
4. 위 계획을 검증
   • 1을 더하는 정도의 연산만 있기때문에, 예외가 있다면 9일때이다.
   • 그마저도 모든 숫자가 9일때 가장 연산이 꼬여버리는데, 이경우는 +2만 하면 펠린드롬수가 되기때문에 초반에 예외처리해주면 된다.
   • 나머지는 자릿수가 홀수, 짝수일때 분기점만 제대로 나누면 오류는 없을거라 생각한다.
5. 계획 수행 (실제코드 작성)
   1. Python 3

      • import sys
        #sys.stdin = open("input.txt")
        input = sys.stdin.readline
        
        def solution(inputNum):
            f = 0
            inputStr = str(inputNum)
            # 9로만 이루어진 숫자이면 2를 더했을때 펠린드롬
            for x in inputStr:
                if x != '9':
                    f = 1
            if f == 0:
                return inputNum + 2
        
            # 1. 문자열을 같은길이의 반으로 나눠서 앞뒤를 비교하며 단순한 펠린드롬을 만들기
            # 즉, inputNum보다 큰 펠린드롬인지는 후에서 판단
            tmp = ""
            for i in range(0, len(inputStr)):
                # 처음에서 i번째 글자보다, 뒤에서 i번째 글자가 크거나 같다면
                if i <= len(inputStr) - 1 - i:
                    # 처음에서 i번째 글자 넣기
                    tmp += inputStr[i]
                else:
                    # 그게 아니라면 뒤에서 i번째 글자 넣기
                    tmp += inputStr[len(inputStr) - 1 - i]
            # 만든 펠린드롬이 문제조건에 충족한다면 바로 답 리턴
            if inputNum < int(tmp):
                return int(tmp)
        
            # 2. 만든 펠린드롬이 inputNum보다 크지 않다면 크게 만들어줘야하는데, 중간글자만 크게하면 됨.
            tmp = ""
            for i in range(0, (len(inputStr) + 1) // 2):
                tmp += inputStr[i]
            tmp = str(int(tmp) + 1)
            for i in range(0, len(inputStr) // 2):
                tmp += tmp[len(inputStr) // 2 - 1 - i]
            return int(tmp)
        
        if __name__ == '__main__':
            inputNum = int(input())
            print(solution(inputNum))

 

 

• 결과

N이 50자리까지도 가기때문에, 이를 바로 한번에 정수형으로 받을 수는 없었다.. 결국 BigInteger나 정수형배열 등으로 받는 방법밖에 없었는데, 파이썬코드처럼 이 사이를 유연히 바꿀수있는 방법을 고민하다가 결국 제대로 풀지 못했다. 

개인적으로.. BigInteger는 정말 해도해도 안되면 해야하는 방법이라 생각했기때문에 쓰지않았는데, 후에 좀더 시도해보다가 깔끔한 코드가 정녕 나오지 않는다면... 위 클래스로 선언하고 풀어보려한다..