다음은 [엘리스] 주간 알고리즘 - 알고리즘 다과회 - [7/31] 모자 사기 좋은 날을 요약한 것이다.

문제

'거울 수’는 올바르게 읽거나 거꾸로 읽어도 같은 수이다.
예를 들어 202는 0, 1, …, 191, 202로 30번째 거울 수이다.
어떤 모자의 고유 번호 N을 입력했을 때, N번째 거울 수를 출력하는 코드를 작성하라.

입력

첫번째 줄에 모자의 고유 번호 N(1≤N≤10,000,000)이 주어진다.

출력

N번째 거울 수를 출력하라.

시행착오

처음에는 0부터 시작하여 N번째 팰린드롬 수를 출력하도록 했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def isPalindrome(n):
	l = len(n)
	for i in range(0, int(l/2)):
		if n[i] != n[l-1-i]:
			return False
	return True

if __name__ == "__main__":
	n = int(input())
	answer = 0
	for i in range(1, n):
		while isPalindrome(str(answer)) is False:
			answer += 1
		answer += 1
	print(answer-1)

시간 복잡도가 O(N×l)인데 마지막 테스트 케이스에서 시간 초과가 뜬다.

따라서 N번째 팰린드롬 수를 바로 반환하는 함수를 만들기로 결심했다.

알고리즘

  • 팰린드롬 수의 몸통은 그 수의 길이가 홀수일 때 정가운데 숫자 한 개를 말한다.
  • 팰린드롬 수의 날개는 그 수의 왼쪽 절반을 말한다. 예를 들어 1221, 12321의 날개는 12이다.
  • 1~10번째 팰린드롬 수인 0~9를 제외했을 때, 다음과 같은 규칙으로 N번째 팰린드롬 수를 구할 수 있다.
    • N은 11부터 시작한다.
    • 길이가 짝수인 팰린드롬 수부터 먼저 세므로 isOdd 플래그의 기본값은 False이다.
    • isOdd가 False일 때. 수의 길이가 짝수일 때.
      • 99...999까지 오면 isOdd 플래그를 반대로 바꾼다.
      • 날개가 1씩 증가한다.
    • isOdd가 True일 때. 수의 길이가 홀수일 때.
      • 몸통과 날개가 모두 9라면 isOdd 플래그를 반대로 바꾼다.
      • 몸통 먼저 1씩 증가하고, 9까지 오면 0이 되고 날개가 1씩 증가한다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def allNine(n):
	while n != 0:
		if n % 10 != 9:
			return False
		n = int(n / 10)
	return True

def nthPalindromeNumber(n):
	if n < 11:
		return n-1
	oddBody = 0
	oddWing = 1
	evenWing = 1
	isOdd = False
	i = 11
	while i != n:
		if isOdd:
			if oddBody == 9:
				if allNine(oddWing):
					isOdd = not isOdd
				oddBody = 0
				oddWing += 1
			else:
				oddBody += 1
		else:
			if allNine(evenWing):
				isOdd = not isOdd
			evenWing += 1
		i += 1
	if isOdd:
		return int(str(oddWing) + str(oddBody) + str(oddWing)[::-1])
	else:
		return int(str(evenWing) + str(evenWing)[::-1])

print(nthPalindromeNumber(int(input())))