[Python] 백준 30446번: 회문수

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

 

[풀이]

문제 조건은 다음과 같았다.

실행시간 1초, 메모리 1024MB, N의 최대 크기 10^10 (100억)

 

단순히 1부터 100억 까지의 숫자를 반복문으로 계산해서 회문을 비교하게 되면, 100초가 걸릴 것이 뻔하다.

(대략 1억에 1초로 친다.)

---

 

그럼 어떻게 해야하나.

우선, 각 숫자 범위마다 회문의 조건을 만족하는 수의 개수를 구해보았다.

 

• 1 ~ 10 : (9개) 1, 2, 3, 4, 5, 6, 7, 8, 9
• 11~100 : (9개) 11, 22, 33, 44, 55, 66, 77, 88, 99
• 101~1000 : (90개) 101, 111, 121, 131, 141, 151, 161, 171, 181, 191, ..., 999
• 1001~10000 : (90개)
• 1만 ~ 10만 : (900개)
• 10만 ~ 100만 : (900개) -> 대략 여기까지는 코드를 작성해서 브루트포스로 확인했다.
• 100만 ~ 1000만 : (9000개) -> 여기부터는 이전 범위 대비해서 2번마다 10배씩 증가하는 패턴을 확인했다.
• 1000만 ~ 1억 : (9000개)
• 1억 ~ 10억 : (90000개)
• 10억 ~ 100억 : (90000개)

이렇게 하면

 

9 + 9 + 90 + 90 + 900 + 900+ 9000 + 9000 + 90000 + 90000

 = 2 * (9 + 90 + 900 + 9000 + 90000)

= 2 * 99999

= 199,998

 

N이 100억일 때, 최대 199,998개의 회문이 나오는 것을 알 수 있다.

또한, 각 범위마다 두 번씩 반복한 개수만큼이 나오는 것을 알 수 있다.

---

 

그럼, 이 다음은 어떻게 해야할까?

확인한 패턴을 통해 직접 회문 숫자를 구현을 했다.

 

일단 베이스가 되는 패턴의 수를 만들어놨다.

result에 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 00, 11, 22, 33, 44, 55, 66, 77, 88, 99] 라는 문자열 형태의 숫자를 넣어놨다.

 

이 숫자들을 기반으로, 앞뒤로 회문이 가능한 숫자를 붙여줄 예정이다.

예를 들어, 0을 기반으로 앞뒤로 1을 붙이면 101, 2를 붙이면 202 같은 형식이다.

 

문자열로 넣은 이유는 00과 같은 숫자가 앞뒤로 숫자가 붙어 처리되어야 하기 때문이다.

또한, 앞서 연산한 0110 같은 수에, 앞뒤로 수를 붙여 101101 같은 수를 구현해야 하기 때문에 문자열로 구현하였다.

 

(어차피, 기본 연산량이 20만에, 문자열로 다 바꾸는 연산을 한 번 더 한다해도 40만 밖에 되지 않는다.)

(이 정도면 상수 시간 안에 해결이 가능할 것이라고 예상)

 

---

 

이후로 반복문을 구현하였다.

첫 번째 반복문은 4번만 반복한다.

9 -> 90 -> 900 -> 9000 -> 90000 으로 가기 위해서는 최대 4번만 반복하면 되기 때문이다.

 

두 번째 반복문은 temp1을 순회한다.

temp1은 이전에 연산했던 패턴에 대해 저장해두는 공간이다.

 

세 번째 반복문은 앞뒤로 회문을 만들기 위한 수를 붙인다.

temp2는 앞뒤로 0을 붙인 수까지 저장한다.

temp3는 앞뒤로 0을 붙인 수를 제외하고 저장한다.

 

때문에, 최종 결과로 쓰일 temp3만이, result에 저장되고

temp2는 다음 패턴을 연산하기 위해서만 사용된다.

 

(어차피, 메모리 공간이 1024MB나 되기 때문에 이런 크기 정도의 공간은 중복해서 사용해도 크게 지장이 없을 것이다)

 

연산이 모두 끝나면, result에서 0과 00을 제거한다.

이후, n 이하의 수를 확인하기 위해 result의 각 수를 int로 형변환 후 n과의 크기비교를 진행한다.

 

answer에 저장되어 있는 크기를 구하면 끝.

(n보다 작은 회문 가능한 수가 저장되어 있다)

 

---

 

결과적으로, n에 무슨 숫자가 들어오든 result는 1부터 100억 까지의 회문 가능한 수를 연산한다.

그리고 나서 answer에 n보다 작은 회문 가능한 수가 필터링 된다.

 

result를 구하기 위한 과정이 상수 시간 안으로 연산이 끝나기 때문에, 

이런 로직 구현이 가능했었다.

 

더 효율적인 코드 구현 방법이 있을까..?

 

 

 

 

[코드]

n = int(input())

result = []
odd = [str(i) for i in range(10)]
even = [i+i for i in odd]

result = odd + even
temp1 = result[:]

for _ in range(4):
    temp2 = []
    temp3 = []
    for i in temp1:
        for j in range(10):
            x = str(j) + i + str(j)
            temp2.append(x)
            if j != 0:
                temp3.append(x)
    result.extend(temp3)
    temp1 = temp2[:]

result.remove('0')
result.remove('00')

answer = []
for i in result:
    x = int(i)
    if x <= n:
        answer.append(x)

print(len(answer))

 

 

[시간복잡도]

O(1)