프로그래밍 면접 문제 24: Find Next Higher Number With Same Digits
프로그래밍 면접 문제 24: Find Next Higher Number With Same Digits
이 글은 블로그 http://www.ardendertat.com/의 프로그래밍 면접에 대한 글을 번역한 글입니다.
이전글 – 프로그래밍 면접 문제 23: Find Word Positions in Text
숫자가 주어지면 주어진 숫자만 사용해서 다음으로 높은 수를 찾는 문제입니다. 예를 들어 주어진 숫자가 1234인 경우 각 자리의 수를 이용해서 다음으로 높은 숫자를 만들면 1243입니다.
단순한 접근 방법으로는 각 자리의 숫자를 사용해서 순열(permutaion)을 생성하고 순서대로 정렬합니다. 그런 다음 정렬된 숫자 목록에서 주어진 숫자를 찾고, 정렬된 순서에서 다음 숫자를 결과로 반환합니다. 이 접근 방법의 복잡도는 순열 단계로 인해 상당히 높습니다. 주어진 숫자 N은 logN + 1 개의 자릿수를 가지므로 O(logN!) 개의 순열이 존재합니다. 순열을 생성한 다음 이를 정렬하는데 O(logN!loglogN!) 개의 작업이 필요합니다. 이를 좀 더 단순화시킬 수 있는데, O(logN)은 O(NlogN)과 동일합니다. 그리고 O(loglogN!)은 O(logN)과 같습니다. 따라서 복잡도는 O(N(logN)^2)가 됩니다.
예제를 이용해서 좀 더 나은 해결방법을 시각화 해보겠습니다. 12543이 주어진 경우, 다음으로 높은 숫자는 13245입니다. 10의 자릿수부터(예제의 경우 4) 왼쪽으로 각 자리에 해당하는 숫자를 확인할 수 있습니다. 각 반복과정에서 현재 확인 중인 자리 위치의 오른쪽 자리에 있는 숫자를 확인하고, 그 오른쪽 숫자의 값이 현재 자리의 값보다 크면 멈추고, 아닌 경우 왼쪽으로 계속 진행합니다. 따라서 예제의 경우, 현재 자리의 숫자 4에서 시작하면 오른쪽 자리의 숫자는 3이고 4 >= 3이기 때문에 계속 진행합니다. 이제 현재 자리의 숫자는 5, 오른쪽 숫자는 4, 5 >= 4이므로 계속 진행합니다. 이제 현재 자리의 숫자는 2, 오른쪽 숫자는 5, 하지만 2 >= 5가 아니기 때문에 멈춥니다. 숫자 2가 우리가 찾는 중심(pivot) 숫자입니다. 2의 오른쪽 숫자 중에서 2보다 큰 수들 중에 가장 작은 숫자를 찾으면 3입니다. 이 부분이 중요한데, 결과로 얻은 중심 숫자보다 큰 수들 중에서 가장 작은 숫자를 찾아야 원래 숫자 다음으로 큰 수를 정확하게 구할 수 있습니다. 이 숫자와 중심 숫자의 자리를 서로 바꾸면, 13542가 됩니다. 중심 숫자는 3입니다. 중심 숫자의 오른쪽 에 있는 모든 숫자를 오름차순으로 정렬하면, 13245를 결과로 얻을 수 있습니다. 구하던 결과를 얻었습니다. 코드는 다음과 같습니다:
def nextHigher(num):
strNum = str(num)
length = len(strNum)
for i in range(length-2, -1, -1):
current = strNum[i]
right = strNum[i+1]
if current < right:
temp = sorted(strNum[i:])
next = temp[temp.index(current) + 1]
temp.remove(next)
temp = ''.join(temp)
return int(strNum[:i] + next + temp)
return num
43221과 같이 주어진 숫자의 각 자릿수가 오른쪽에서 왼쪽으로 단조롭게 증가하는 경우, 해당 숫자가 각 자릿수를 조합해서 얻을 수 있는 숫자 중 가장 높은 숫자이기 때문에 어떤 작업도 수행하지 않습니다. 더 높은 숫자가 없으므로 주어진 숫자를 그대로 반환합니다. 또한 7과 같이 한 자리의 숫자 역시 동일한 경우가 발생합니다. 숫자가 하나 밖에 없기 때문에 다른 숫자를 형성할 수 없습니다.
이 알고리즘의 복잡도 역시 주어진 숫자의 자릿수에 따라 달라지며 정렬 부분도 큰 영향을 줍니다. 주어진 숫자 N은 logN + 1개의 자릿수를 가졌고 최악의 경우 logN 개의 자릿수를 정렬해야 합니다. 예를 들어 1987과 같이, 왼쪽 끝 자리의 숫자를 제외하고 오른쪽에서 왼쪽으로 숫자가 점점 커지는 숫자에서 최악의 경우가 발생합니다. 정렬을 위해 복잡도가 O(KlogK)인(K는 정렬할 요소의 수) 퀵정렬, 병합정렬, 힙정렬과 같은 비교 기반 알고리즘을 사용할 필요는 없습니다. 각 자리의 숫자가 항상 0에서 9사이의 숫자인 것을 알기 때문에 선형적인 O(K)의 복잡도로 작업을 할 수 있는 계수 정렬(counting sort), 기수 정렬(radix sort), 버킷 정렬(bucket sort)를 사용할 수 있습니다. 따라서 logN 자릿수를 정렬하는 전체 복잡도는 O(logN)의 선형적인 결과를 유지합니다. 각 자릿수를 적어도 한번은 확인해야 하기 때문에 이 복잡도는 최적입니다.
