[프로그래머스/Day 6] 3진법 뒤집기 - pow()를 함부로 쓰면 안되는 이유

1) 문제 상황: 정답인데 시간 초과

#include <vector>
#include <cmath>

using namespace std;

// 1. n이 1이 될때까지
//    1-1. n % 3의 결과를 배열에 넣는다.
//    1-2. n / 3을 한다.
// 2. 배열에 n을 넣는다. (이때의 n은 1)
// 3. 배열은 이미 앞뒤 반전이 일어난 상태이므로 첫번째 값부터 반복문을 돌려 값을 결과에 더한다.
//    더하는 값 = 현재 인덱스의 값 * 3^(배열의 크기 - 인덱스 - 1)
int solution(int n) {
    int answer = 0;
    const int BASE = 3; 
    vector<int> numbers;

    while(n != 1)
    {
        numbers.push_back(n % BASE);
        n /= BASE;
    }

    numbers.push_back(n);

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

    return answer;
}

---

2) 입력값 분석 없이 풀면 생기는 함정

• 입력값의 크기는 1 이상 1억 이하
• 반복 횟수 자체는 진법 변환이므로 O(log₃N) 수준이라 충분히 작다.
• 그런데도 시간 초과가 나는 경우가 있다.

---

3) 시간 초과의 원인: pow()

• 현재 반복문은 O(log₃N) 이지만,
• 매 반복마다 호출하는 pow(BASE, k)는:
  • 부동소수(double) 기반 계산
  • 내부적으로 비싼 연산(거듭제곱 계산)
  • 결과는 다시 int로 합산 (캐스팅 비용 + 안정성 문제 가능)
• 즉, “반복 횟수”가 아니라 반복문 안의 연산 비용이 커서 TLE가 발생한다.

---

4) 해결 1: pow() 없이 자리값을 정수로 누적하기

#include <vector>
using namespace std;

// 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을 곱한다.
int solution(int n) {
    vector<int> numbers;
    const int BASE = 3;
    while (n > 0) {
        numbers.push_back(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;
}

• 핵심은 place를 1 → 3 → 9 → 27 ...처럼 정수로 직접 키워가는 것
• pow() 제거로 연산 비용이 급감한다.

---

5) 해결 2: 변환 + 뒤집기 + 복원을 한 루프로 끝내기

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

• n % 3으로 나오는 값들은 이미 “뒤집힌 3진수의 자리” 순서
• 그래서 배열 저장 없이,
  • ans = ans * 3 + digit 형태로 즉시 누적하면 끝
• 공간도 줄고, 코드도 짧고, 속도도 가장 안정적이다.

---

6) 결론

• 시간 초과는 보통 “반복 횟수” 때문이 아니라
  반복문 내부에서 호출하는 무거운 연산(pow) 때문일 수 있다.
• 진법 변환류 문제는:
  • pow() 대신 정수 누적
  • 가능하면 한 루프로 변환+복원까지 끝내기
    가 가장 깔끔한 정답이다.