문제 개요
정수 n이 주어졌을 때, n을 k진수(k ≥ 2)로 나타냈을 때 모든 자릿수가 1이 된다면 k를 n의 "좋은 기반(good base)"이라고 부릅니다. 숫자 n이 문자열 형태로 주어지면, 가능한 좋은 기반 중 가장 작은 값을 문자열로 반환해야 합니다.
예를 들어 n이 121이라면 정답은 3입니다. 121을 3진수로 표현하면 11111이 되는데, 실제로 1 + 3 + 9 + 27 + 81 = 121이 성립하기 때문입니다.
핵심 아이디어
밑이 k이고 자릿수가 m개인 "모두 1"로만 이루어진 수는 다음과 같은 등비수열의 합으로 표현할 수 있습니다.
n = 1 + k + k² + … + km−1
따라서 자릿수 m을 하나 정한 뒤, 위 식을 만족하는 k를 이분 탐색(binary search)으로 찾으면 됩니다. 자릿수가 길어질수록 필요한 밑 k는 작아지므로, m을 큰 값(64)부터 작은 값 순서로 검사하면 처음 발견되는 밑이 곧 가장 작은 좋은 기반이 됩니다. 만약 세 자리 이상의 표현에서 적절한 밑을 찾지 못했다면, 두 자리 표현("11", 즉 밑이 n−1)은 항상 성립하므로 n − 1을 반환하면 됩니다.
풀이 단계
- getSum(x, length): 밑이 x이고 자릿수가 length개일 때 "모두 1" 수의 실제 값을 계산합니다. mainSum := 0, temp := 1로 초기화한 뒤 length번 반복하면서 mainSum에 temp를 더하고 temp에 x를 곱한 후 mainSum을 반환합니다.
- check(n, length): low := 1, high := n으로 설정하고 이분 탐색을 수행합니다. mid에 대해 getSum(mid, length)를 계산하여 그 값이 n과 같으면 mid를 반환하고, n보다 크면 high를 mid − 1로 줄이고, n보다 작으면 low를 mid + 1로 늘립니다. 탐색이 끝날 때까지 찾지 못하면 −1을 반환합니다.
- smallestGoodBase(n): i를 64부터 1씩 감소시키며 check(n, i)를 호출하고, 결과가 2 이상이면 해당 값을 문자열로 변환해 반환합니다. 모든 시도가 실패하면 n − 1을 문자열로 반환합니다.
Python 구현 예제
class Solution(object):
def getSum(self, x, length):
mainSum = 0
temp = 1
for _ in range(length):
mainSum += temp
temp *= x
return mainSum
def check(self, n, length):
low = 1
high = n
while high >= low:
mid = low + (high - low) // 2
mainSum = self.getSum(mid, length)
if mainSum == n:
return mid
elif mainSum > n:
high = mid - 1
else:
low = mid + 1
return -1
def smallestGoodBase(self, n):
n = int(n)
for i in range(64, 0, -1):
x = self.check(n, i)
if x >= 2:
return str(x)
return str(n - 1)
ob = Solution()
print(ob.smallestGoodBase("121"))
입력 및 출력
입력:
"121"
출력:
3
121을 3진수로 표현하면 11111이 되어 모든 자릿수가 1이므로, 가장 작은 좋은 기반인 3이 출력됩니다.
복잡도 분석
getSum은 자릿수 m에 비례하는 O(m) 시간이 소요되고, check는 이분 탐색을 사용하므로 O(m · log n)이 걸립니다. 검사해야 할 자릿수 후보가 최대 64개이므로 전체 시간 복잡도는 대략 O(64 · 64 · log n) 수준으로, n이 최대 1018 범위라도 충분히 빠르게 동작합니다.