[programmers][월간 코드 챌린지 시즌1] 3진법 뒤집기

문제 : programmers.co.kr/learn/courses/30/lessons/68935

---

string third;
while(n > 0) {
  third += n % 3;
  n /= 3;
}

int mul = 1;
int answer = 0;
// 뒤에서부터 탐색
for(int i=third.size()-1; i>=0; i--){ 
  answer += mul * third[i];
  mul = 3 * mul;
}

n이 0이 될때까지 n에 3나머지 연산한 결과를 문자열 앞에서부터 추가하고 n에 3을 나눈다.

n이 0이 되었을 때의 문자열이 n을 3진법화한 결과이고 이를 앞뒤 반전하라고 했으므로 뒤에서부터 3의 i(i는 자리수-1)승을 곱한 수의 총합이 정답이 된다.

 

시간복잡도는 O(log3N)

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/programmers/%EC%9B%94%EA%B0%84%20%EC%BD%94%EB%93%9C%20%EC%B1%8C%EB%A6%B0%EC%A7%80%20%EC%8B%9C%EC%A6%8C1/3%EC%A7%84%EB%B2%95%20%EB%92%A4%EC%A7%91%EA%B8%B0.cpp