프로그래머스 Lv.1 - 3진법 뒤집기

출처: https://school.programmers.co.kr/learn/courses/30/lessons/68935

3진법 문자열을 만들어 뒤집고 다시 파싱할 필요가 없는 문제다. n % 3으로 하위 자릿수부터 뽑아 answer = answer * 3 + 자릿수로 쌓으면, 낮은 자리가 먼저 높은 자리에 들어가면서 자릿수 뒤집기가 저절로 된다.

// 프로그래머스 Lv.1 - 3진법 뒤집기
// https://school.programmers.co.kr/learn/courses/30/lessons/68935
//
// [문제]  n을 3진법으로 바꿔 앞뒤로 뒤집은 뒤 다시 10진법으로 표현한 수를 반환
// [제약]  n은 1 이상 100,000,000 이하의 자연수
// [입출력]  45 → 7 / 125 → 229
//
// 풀이: n%3로 하위 자릿수부터 뽑아 answer=answer*3+자릿수로 쌓으면
//        자동으로 자릿수가 뒤집힌 3진수가 만들어진다 — O(log₃ n)

#include <string>
#include <vector>

using namespace std;

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

핵심 요약 — 진법 뒤집기는 문자열 변환 없이 나머지 연산만으로 끝난다. 하위 자릿수부터 뽑아 answer * 3 + 자릿수로 누적하면 뒤집힌 3진수가 곧바로 10진값이 된다. 시간복잡도는 O(log₃ n).