[프로그래머스/Day 7] 3진법 뒤집기 - 진법 변환, 뒤집기, 호너의 법칙

기존 코드

// 1. n이 0이 될 때까지 반복한다.
//    1-1. n을 3으로 나눈 나머지를 문자열에 저장한다.
//         → 3진법 변환 과정이며, 이 값들은 뒤집힌 순서로 저장된다.
//    1-2. n을 3으로 나눈 몫으로 갱신한다.
// 2. 문자열에는 뒤집힌 3진수 각 자리가 저장되어 있다.
// 3. 문자열의 마지막 인덱스부터 순회하며 10진수로 복원한다.
//    3-1. 현재 자리값(place)은 3의 거듭제곱을 의미한다.
//    3-2. answer += 현재 자리 숫자 × place
//    3-3. 다음 자리를 위해 place에 3을 곱한다.
#include <string>
using namespace std;

int solution(int n) {
    string numbers = "";
    const int BASE = 3;
    while (n > 0) {
        numbers += n % BASE;
        n /= BASE;
    }

    int answer = 0;
    int place = 1;
    for (int i = (int)numbers.size() - 1; i >= 0; --i) {
        answer += numbers[i] * place;
        place *= BASE;
    }

    return answer;
}

• pow() 함수는 실수형(double)을 반환하여 연산 비용이 크다. place에 기수(Base)를 곱해 나가는 방식이 속도가 빠르고 부동소수점 오차 걱정도 없는 정석적인 테크닉이다.
• 현재 자릿수 값: n % base
• 다음 자릿수로 이동: n / base
• 추출, 데이터를 쌓는 것이 뒤집기 효과를 낸다.

---

개선 코드

#include <string>
using namespace std;

int solution(int n) {
    string numbers = "";
    const int BASE = 3;
    while (n > 0) {
        numbers += n % BASE;
        n /= BASE;
    }

    int answer = 0;
    for(char number : numbers)
    {
        answer = answer * 3 + number;
    }

    return answer;
}

• 호너의 법칙: 앞에서부터 읽으면서 기존 값에 진법을 곱하고 더하는 방식
• place 변수 없이 구현할 수 있다.