[ Codeforces - Codeforces Round #802 (Div. 2) (06/26) ] - #B Panlindromic Numbers(Python)

• 문제링크

https://codeforces.com/contest/1700/problem/B

Problem - B - Codeforces

 

 

 

• 문제

 

 

 

• 시행착오

값을 하나씩 증가시키면서 찾아야한다는 것에 사로잡혀서 시간초과의 덫을 빠져나오지 못했다.. 이 문제에서는 가능한 어떤 결과라도 답으로 인정해준다는 문구를 이용하지 못하고 정석대로만 시도했던 것 같다. 문제에서 주어진 바를 다 이용하여 빈틈을 찾을 수 있는 프로그래머가 되기 위해 열심히 해야겠다..!

 

 

 

• 문제분석

t : 입력 테스트 케이스 개수

n : 출력할 문자열의 길이

num : 자연수

를 입력받아 회문을 만들어야한다. 여기서 회문이란 12321처럼 뒤집은 숫자가 원래숫자가 되는 수를 말한다. 위 문제를 풀기 위해서는 회문의 특징뿐만 아니라 어떻게하면 임의의 수에서 빠르게 회문을 만들 수 있는지를 생각하는 게 중요하다.

 

 

 

• 각 파라미터의 유형

t = 3

<조건> 

→  1 ≤ t ≤ 100

=> 테스트 케이스를 나타내며, 위의 조건을 충족한다.

 

n = 2

<조건> 

→  2 ≤ n ≤ 100,000

=> 출력해야할 문자열의 글자길이를 나타내며, 위의 조건을 충족한다.

 

num = 99

<조건> 

→  0이 아닌 양의 정수

=> 더해서 회문을 만들어야하는 기준 값이며, 위의 조건을 충족한다.

 

 

 

• 문제접근

※ 작성자가 문제를 보고 든 생각을 차례대로 써본 것이다. 이 순번은 정답이 아니며 매번 다른 생각을 해보길 권장한다.

 

1) num 숫자와 출력해야할 숫자의 합이 회문이 되어야하는데, 글자길이는 n으로 정해져 있으므로 n의 글자수를 맞추기 위해 10**n부터 시작하여 반복문을 돌려야한다고 생각했다.

for i in range(int(input())):
    n=int(input());m=int(input())    
    s=str(m+10**(n-1))
    while s[:len(s)//2] != s[::-1][:len(s)//2]:
        s=str(int(s)+1)
    print(int(s)-m)

정말 당연하게도 시간초과가 발생했다.. 이 코드에서 여러번 바꿔보고 시간초과의 늪에 빠져있던 때, 답이 여러개면 그중 어떤 하나라도 출력하면 된다는 문구를 보았고 최적화된 답을 빠르게 반복문 없이 규칙을 찾아 구해보자는 생각을 하게 되었다.

 

2) 쉽사리 생각이 떠오르지 않았고 계속 고민하던 도중, 반대로 회문을 임의의 값으로 설정한 뒤 거기서 입력받은 값을 빼면 된다는 생각을 하게되었다. 11, 111, 1111 ...은 전부 회문이므로 여기에서 입력한 값을 뺐을때 그 값이 출력값이 되도록 구현하면 될것 같았다.

# 틀린코드
for _ in range(int(input())):
    n = int(input())
    N = input()
    s="1"
    for i in range(n,int(N)+1):
        ans = int(s*i)-int(N)
        print(ans)
        if ans>0 and len(str(ans))==n:
            print(ans)
            break

하지만 n=4, N=1023이 들어올 경우 ans가 1111일때는 최종값이 99인데 4글자가 아니므로 탈락, ans가 11111일때는 최종값이 10088인데 4글자가 아니고 심지어 5글자로 초과되어 값을 구할 수 없었다.

 

3) 위의 코드를 통해 결국은 1이 아닌 가장 큰값 9를 기본으로 잡는것이 적당하다고 보여졌다. 하지만 위의 코드에서 s="1"을 s="9"로 바꾼다면 n=2, N=99가 들어올경우 0을 출력하게 되는데 이 문제의 조건에서 출력은 0이 될 수 없다고 쓰여있었다. 그래서 이 부분을 예외처리를 해주고 나머지는 그대로 출력하면 된다고 생각했다.

=> 그렇게 최종코드가 나오게 되었다.

 

 

• 최종코드

for _ in range(int(input())):
    t = int(input())
    n = input()
    if n[0] == '9':
        print((10 ** (t + 1) - 1) // 9 - int(n))
    else:
        print((10 ** t) - 1 - int(n))