4096. [Python]팰린드로미터

1. 문제

 

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

4096번: 팰린드로미터

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 128MB
• 브루트포스

 

3. 파이썬 코드

 

while True:
    num = input()
    # input 값이 0 이면 반복문 탈출
    if num == "0":
        break
    else:
        # 몇번 더했는지 확인하는 변수
        cnt = 0
        # 초기의 길이를 체크
        num_length = len(num)
        # 1씩 계속 더해나감
        while True:
            # 앞뒤가 같은지 확인
            if num[::] == num[::-1]:
                # 같으면 몇번 더했는지 출력
                print(cnt)
                break
            # 아닐경우
            else:
                # 이전의 값에 1을 계속 더해나감
                num = str(int(num) + 1)
                # 만약 길이가 처음 길이보다 작아졌을 경우 앞에 0을 차이만큼 추가해줌
                if len(num) < num_length:
                    num = num[::-1]
                    num += "0"*(num_length-len(num))
                    num = num[::-1]
            cnt += 1

 

4. 문제를 풀고난 후 생각

 

• 문제에 적힌 내용 그대로 구현을 진행한다고 굉장히 많은 시도를 했었다.

• 한 3일정도 잡고 풀었던 것 같지만 오늘 해결했는데 해결방법은 단순했다.
• 들어온 숫자부터 1씩더해나가며 앞이랑 뒤가 같은지 확인해본 후 같으면 몇번 횟수를 진행했는지를 출력해준 후 무한루프를 탈출하는 것이다.
• 되게 간단한 문제지만 있는 그대로 구현을 할려고 시도를 하다보니 길이가 1900자 정도로 매우 길어진 느낌이다.
• str 에서 int 로 변경할 경우 주의할 점은 "000121"등이 올 경우 int 형으로 변하면 121이 되므로 초기 문자의 값의 길이를 체크해둔 후 int로 변하고 다시 str로 변환하는 과정에서 길이를 확인한 후 그 차이만큼 앞에 "0"을 더해주는 식으로 구현했다.
• 무작정 1씩 더해나가는 것은 시간초과가 나지 않을까? 라는 생각도 해봤지만 예를 들어 값이 "1,000,000"이 올 경우 결국 1씩 더해나가도 대략 1,000,000 ** 0.5 정도의 연산만 시행해도 답이 나올 것 같아서 구현해 봤더니 맞았다.
• 처음 시도했던 코드랑 새로 짠 코드를 비교해봐도 스스로가 어리석었다.

while True:
    num = input()
    if num == "0":
        break
    else:
        num_length = len(num)
        if num_length % 2 == 0:
            meter = num[:num_length//2]
            meter = meter[::-1]
            need = num[num_length//2:]
            meter_length = len(meter)
            if int(meter) > int(need):
                print(int(meter)-int(need))
            elif int(meter) == int(need):
                print(0)
            else:
                meter = meter[::-1]
                meter = str(int(meter)+1)
                meter = meter[::-1]
                answer_number = 10**meter_length
                answer = answer_number - int(need)
                if len(meter) < meter_length:
                    meter = meter[::-1]
                    meter += "0"*(meter_length-len(meter))
                answer += int(meter)
                print(answer)
        else:
            meter = num[:num_length//2]
            middle = num[num_length//2]
            meter = meter[::-1]
            need = num[(num_length//2)+1:]
            meter_length = len(meter)
            if int(meter) > int(need):
                print(int(meter)-int(need))
            elif int(meter) == int(need):
                print(0)
            else:
                if middle == "9":
                    meter = meter[::-1]
                    meter = str(int(meter)+1)
                    meter = meter[::-1]
                    if len(meter) < meter_length:
                        meter += "0"
                    print((10**meter_length)-int(need)+int(meter))
                else:
                    answer_number = 10**meter_length
                    answer = answer_number - int(need)
                    if len(meter) < meter_length:
                        meter = meter[::-1]
                        meter += "0"*(meter_length-len(meter))
                    answer += int(meter)
                    print(answer)

 

 

5. 문제를 푸는데 도움이 되는 지식

 

• 브루트 포스
• 구현