[TIL #20] 3진법 뒤집기

자연수 $n$이 주어질 때,

$n$을 삼진법으로 변환 후 순서를 뒤집고 다시 십진수로 바꾸는 문제.

 

삼진수를 문자열로 표현하여 처리하면 되지 않을까 했다.

 

#include <string>

using namespace std;

string toTernary(int n) {
    if (n == 0) return "0";

    string ternary = "";
    while (n > 0) {
        ternary = to_string(n % 3) + ternary;
        n /= 3;
    }

    return ternary;
}

int toDecimal(const string& ternary) {
    int decimal = 0;
    int power = 1;

    for (int i = ternary.length() - 1; i >= 0; --i) {
        int digit = ternary[i] - '0';
        decimal += digit * power;
        power *= 3;
    }

    return decimal;
}

int solution(int n) {
    string tmp = toTernary(n);
    return toDecimal(tmp);
}

좀 길어진 감이 있지만 역할을 충분히 수행할 수 있다.

 

하지만 최적해가 아니라는 것은 충분히 느낄 수 있었다.

다른 사람의 풀이를 봐도 뭔가 만족스럽지 않았다.

문자열 대신 벡터를 활용하는 것은 대단히 인상적이었지만...

 

요즘은 AI 시대가 아니던가.

얼마나 기똥찬 대답을 내놓을까 기대를 하며 물어봤다.

 

그리고 AI는 다음과 같은 답을 내놓았다.

int solution(int n) {    
    while (n > 0) {
        result = result * 3 + (n % 3);
        n /= 3;
    }
    
    return result;
}

난 정말 충격적이었다.

장황한 코드가 반복문 하나로 압축됐다.

 

벡터나 스트링 등을 사용하지 않아 공간복잡도 문제가 해결됐고,

정수 연산만 사용해 시간복잡도가 대단히 개선됐다.

코드가 짧아져 보기에도 편해졌다.

 

AI는 다음과 같이 설명했다.

 

---

1. 3진법 변환과 동시에 뒤집기:
   - 기존 방식에서는 n을 3으로 나눈 나머지를 차례로 구해 문자열의 앞쪽에 추가했습니다(예: 45 -> "1200").
   - 이 코드에서는 n % 3으로 나머지를 구한 후, 기존 result에 3을 곱하고 나머지를 더합니다.
   - 이 과정은 자연스럽게 3진법 숫자를 뒤집는 효과를 가집니다.

2. 뒤집힌 3진법 수를 10진법으로 변환:
   - result *= 3는 기존 자릿수를 한 단계씩 올리는 역할을 합니다.
   - (n % 3)를 더하는 것은 새로운 1의 자리 숫자를 추가하는 것과 같습니다.
   - 이 과정이 반복되면서 자연스럽게 10진법으로의 변환이 이루어집니다.

예시로 살펴보겠습니다 (n = 45의 경우):

1. 초기 상태: n = 45, result = 0
2. 첫 번째 반복:
   - result = 0 * 3 + (45 % 3) = 0 + 0 = 0
   - n = 45 / 3 = 15
3. 두 번째 반복:
   - result = 0 * 3 + (15 % 3) = 0 + 0 = 0
   - n = 15 / 3 = 5
4. 세 번째 반복:
   - result = 0 * 3 + (5 % 3) = 0 + 2 = 2
   - n = 5 / 3 = 1
5. 네 번째 반복:
   - result = 2 * 3 + (1 % 3) = 6 + 1 = 7
   - n = 1 / 3 = 0 (루프 종료)

최종 result는 7이 되며, 이는 45를 3진법으로 변환(1200), 뒤집고(0021), 다시 10진법으로 변환한 결과와 동일합니다.

이 방식이 작동하는 핵심은 3진법의 각 자릿수를 역순으로 처리하면서 동시에 10진법으로 변환한다는 점입니다. 각 단계에서 이전 결과에 3을 곱하는 것은 3진법에서의 자릿수 이동을 나타내며, 새로운 나머지를 더하는 것은 새로운 3진법 숫자를 추가하는 것과 같습니다.

이렇게 하여 별도의 문자열 조작이나 추가적인 변환 과정 없이 한 번의 루프로 모든 작업을 수행할 수 있게 됩니다.

---

 

나 혼자서 이런 방법을 떠올릴 수 있었을까?

AI가 인사이트를 주는 데 큰 역할을 하는 것 같다.