문제 소개
하나의 정수 n이 주어졌을 때, 이 숫자를 3진수(base 3)로 변환한 결과를 문자열 형태로 구하는 것이 목표입니다.
예를 들어 입력이 17이라면 출력은 "122"가 됩니다. 실제로 17은 1×3² + 2×3¹ + 2×3⁰ = 9 + 6 + 2 = 17이므로, 3진수로 표현하면 122에 해당합니다.
해결 알고리즘
10진수를 임의의 진법으로 변환할 때 가장 널리 쓰이는 방식은 반복적인 나눗셈과 나머지 계산입니다. 참고로 파이썬에는 2진수를 위한 bin(), 16진수를 위한 hex() 같은 내장 함수가 있지만, 3진수를 위한 내장 함수는 제공되지 않기 때문에 직접 구현해야 합니다. 절차는 다음과 같습니다.
- 부호 처리: n이 음수라면 부호('-')를 미리 저장해 둡니다. 양수라면 빈 문자열을 사용합니다.
- n의 절댓값을 기준으로 계산을 진행합니다.
- n이 3보다 작으면 한 자릿수이므로 그대로 문자열로 반환합니다.
- 결과를 담을 빈 문자열 s를 준비한 뒤, n이 0이 아닌 동안 다음을 반복합니다.
- n을 3으로 나눈 나머지(n mod 3)를 문자열로 바꿔 s의 앞에 붙입니다.
- n을 3으로 나눈 몫(n // 3)으로 갱신합니다.
- 반복이 끝나면 저장해 둔 부호와 s를 이어 붙여 최종 결과를 반환합니다.
구현 예제
class Solution:
def solve(self, n):
sign = '-' if n < 0 else ''
n = abs(n)
if n < 3:
return str(n)
s = ''
while n != 0:
s = str(n % 3) + s
n = n // 3
return sign + s
ob = Solution()
print(ob.solve(17))
실행 결과
입력:
17
출력:
122
동작 원리 살펴보기
n = 17일 때 코드의 실행 흐름을 단계별로 확인해 보겠습니다.
- 17 ÷ 3 = 몫 5, 나머지 2 → s = "2"
- 5 ÷ 3 = 몫 1, 나머지 2 → s = "22"
- 1 ÷ 3 = 몫 0, 나머지 1 → s = "122"
- n이 0이 되어 반복이 종료되고, 최종적으로 "122"를 반환합니다.
나머지를 매번 문자열의 앞쪽에 추가하는 이유는, 나눗셈 과정에서 낮은 자릿수부터 먼저 계산되기 때문입니다. 이렇게 하면 올바른 자릿수 순서를 자연스럽게 유지할 수 있습니다.
이 알고리즘의 시간 복잡도는 O(log₃ n)으로, 숫자를 3으로 계속 나누기 때문에 자릿수에 비례하는 매우 효율적인 방식입니다. 또한 음수 입력에 대해서도 부호만 분리해 처리하므로 모든 정수에 대해 안전하게 동작합니다.