프로그래밍 면접 문제 19: Find Next Palindrome Number
프로그래밍 면접 문제 19: Find Next Palindrome Number
이 글은 블로그 http://www.ardendertat.com/의 프로그래밍 면접에 대한 글을 번역한 글입니다.
이전글 – 프로그래밍 면접 문제 18: Find Even Occurring Element
주어진 숫자보다 큰 수들 중에서 가장 작은 대칭수(Palindrome Number)를 찾는 문제입니다. 예를 들어 125가 주어졌을 때, 이 수보다 크지만 가장작은 대칭수는 131입니다.
단순한 접근 방법 중 하나는 대칭수를 찾을 때까지 수를 하나씩 증가시키는 방법입니다. 따라서 숫자를 증가시킬 때마다 해당 수가 대칭수인지 아닌지 확인합니다. 이 방법은 가장 직관적이지만, 최적의 방법은 아닙니다. 이 방법의 복잡도는 수의 자릿수에 영향을 받습니다. 6자리인 경우에는 다음 대칭수를 얻기 위해 최악의 경우(999000에서 999999까지) 999를 증가시켜야 합니다. 따라서 이 방법의 복잡도는 O(sqrt(N)) 이며, 상당히 비효율적입니다. 그 대신, 주어진 수의 자릿수에 비례하며 O(logN)의 복잡도를 갖는 방법으로 이 문제를 해결할 수 있습니다.
주어진 수의 자릿수가 홀수인지 짝수인지에 여부에 따라서 두 가지 경우가 존재합니다. 홀수의 경우를 분석하는 것부터 시작해 보겠습니다. 주어진 수가 ABCDE라고 가정할 때, 이 수에서 얻을 수 있는 가장 작은 대칭수는 ABCBA입니다. 이는 가운데 수를 기준으로 왼쪽 오른쪽으로 수를 대칭 시켜서 만들 수 있습니다(왼쪽의 수를 오른쪽으로 순서를 바꿔 반대로 복사해서 만들 수 있습니다). 이 방법으로 수를 만들면 항상 대칭이지만, 원래 수보다 크지 않을 수 있습니다. 일단 대칭수를 만들고 이 수가 원래 수보다 크면 그대로 반환하고, 크지 않은 경우 수를 증가시킵니다. 하지만 어느 자릿수를 증가시켜야 할까요? 왼쪽 절반을 차지하는 수를 증가시키면 수가 너무 커지고, 원래 수보다는 크지만 대칭수 중에서 가장 작은 수를 찾고 있기 때문에, 왼쪽 절반은 증가시키지 않습니다. 오른쪽 절반을 증가시키는 경우, 수의 증가량은 훨씬 낮추지만, 대칭수를 유지시키기 위해서는 왼쪽 절반도 증가시켜야하기 때문에 결국 수가 너무 커지게 됩니다. 따라서 중간에 있는 수를 하나씩 증가시키고, 이 경우에는 100을 더합니다. 이 방법을 사용하면 대칭수가 유지되고, 항상 원래 수보다 큰 결과를 얻을 수 있습니다.
의심되는 부분을 명확히 해줄 몇 가지 예를 들어보겠습니다. 250이 주어졌다고 가정할 때, 가운데 수를 기준으로 왼쪽 수를 대칭시켜서 대칭수를 만들면, 252를 얻을 수 있습니다. 252는 250보다 크므로 원래 수보다 큰 수 중에서 가장 작은 대칭수입니다. 이제 123이 주어졌다고 가정했을 때, 대칭수를 만들면 121을 얻을 수 있고, 이는 원래 수보다 작습니다. 따라서 가운데 자릿수를 하나 증가시키면, 131을 결과로 얻을 수 있습니다. 131 역시 원래 수보다 큰 수중에 가장 작은 대칭수입니다. 하지만, 가운데 자릿수가 9이고 대칭수를 만들었을 때 원래 수보다 작은 결과가 나오는 경우는 어떻게 해야할까요? 이런 경우에는 단순히 가운데 자릿수를 증가시키는 방법은 통하지 않습니다. 이런 경우에 해결 방법은 먼저 반올림을 하면 위의 방법을 적용할 수 있습니다. 예를 들어 주어진 수가 397인 경우, 대칭수를 만들면 393으로, 원래 수보다 작습니다. 따라서 400으로 반올림하고 처음에 주어진 수가 400인 것처럼 문제를 해결합니다. 대칭수를 만들면 404가 되어 원하는 결과를 얻을 수 있습니다.
이제 주어진 수의 자릿수가 짝수인 경우를 분석해 보겠습니다. 주어진 수가 ABCD라고 가정해 보겠습니다. 자릿수가 홀수인 경우와 유사하게, 이 수에서 얻을 수 있는 가장 작은 대칭수는 ABBA입니다 (물론 ABBA의 노래도 훌륭합니다). 이번에도 역시 가운데를 기준으로 왼쪽에서 오른쪽으로 대칭을 만들어서 결과를 얻었습니다. 하지만, 수의 자릿수가 짝수이기 때문에 가운데 수가 이제 두 번째(C, 10의 자리)와 세 번째(B, 100의 자리) 자릿수에 놓입니다(오른쪽에서 1부터 시작). 따라서 이 경우 가운데 두 자릿수인 2번째와 세번째 자릿수를 가운데 수로 정의해 보겠습니다. 이 때 다음 대칭수를 찾기 위한 전략은 다음과 같습니다. 먼저 가운데 수를 기준으로 대칭수를 만들고 이 수가 원래 수보다 큰지 확인합니다. 원래 수보다 크면 이 대칭수를 반환하고, 원래수보다 크지 않으면 가운데 두 수를 1씩 증가시킵니다. 예시의 경우, 110을 더한다는 의미입니다. 이제 예제 몇가지를 살펴보겠습니다.
4512가 주어졌다고 가정할 때, 가운데 수를 기준으로 대칭수를 만들면 4554를 얻을 수 있습니다. 이 수는 원래 수보다 크기 때문에 원하는 결과를 얻었습니다. 이제 주어진 수가 1234라고 해보면, 가운데 수를 기준으로 대칭수를 만들면 1221이고 이는 원래 수보다 작습니다. 따라서 가운데 두 수를 증가시켜서 1331을 만들면 원하는 결과를 얻을 수 있습니다. 그렇다면 대칭수의 가운데 수가 9이고 이 대칭수가 원래 수보다 작은 경우에는 어떻게 해야할까요? 이런 경우 역시 수를 반올림 한 다음, 처음에 반올림 한 수가 주어졌던 것 처럼 문제를 풀어가면 됩니다. 예를 들어, 1997이 주어진 경우, 대칭수를 만들면 1991이 되어 원래 수보다 작습니다. 따라서 반올림해서 2000으로 만들고 이 수가 원래 수라고 가정하고 문제를 해결합니다. 2000의 대칭수를 만들어보면 2002가 되고 이 수는 원래 수보다 크기 때문에 원하는 결과를 얻었습니다. 다음 코드를 살펴보면 지금까지 설명한 내용을 명확하게 확인할 수 있습니다.
def nextPalindrome(num):
length = len(str(num))
oddDigits = (length%2!=0)
leftHalf = getLeftHalf(num)
middle = getMiddle(num)
if oddDigits:
increment = pow(10, length/2)
newNum = int(leftHalf + middle + leftHalf[::-1])
else:
increment = int(1.1 * pow(10, length / 2))
newNum = int(leftHalf + leftHalf[::-1])
if newNum > num:
return newNum
if middle != '9':
return newNum + increment
else:
return nextPalindrome(roundUp(num))
def getLeftHalf(num):
return str(num)[:len(str(num)) / 2]
def getMiddle(num):
return str(num)[(len(str(num)) - 1) / 2]
def roundUp(num):
length = len(str(num))
increment = pow(10, ((length / 2) + 1))
return ((num/increment) + 1) * increment
대칭수를 만드는 과정의 복잡도는 주어진 수의 자릿수에 비례하기 때문에 이 알고리즘의 복잡도는 O(logN)입니다. 최악의 경우에는 모든 숫자를 확인해야하기 때문에, 이 방법이 최적의 방법이라고 할 수 있습니다. 이 방법은 직관적인 방법보다 훨씬 효율적입니다. 주어진 수가 백만인 경우 직관적인 방법을 사용하면 1000개의 처리 과정이 필요한데, 이 방법을 사용하면 10개의 처리 과정이 필요하기 때문에 훨씬 효율적입니다.
이 문제는 간단한 수학과 창의적은 사고력을 필요로 하기 때문에 개인적으로 좋아하는 문제입니다.
