프로그래머스 - 1단계 - 3진법 뒤집기

https://programmers.co.kr/learn/courses/30/lessons/68935#

코딩테스트 연습 - 3진법 뒤집기

- 문제 파악

정수 n을 3진법으로 표현한 뒤 3진법을 뒤집은 값을 10진수로 출력하라

 

- 정답

1. n을 넘지 않는 3의 제곱수를 구한다.

2. 1번에서 구한 3의 제곱수에서 n을 뺀다.

3. 만약 2번을 진행했음에도 3의 제곱수를 한번 더 뺄 수있다면 뺀다.

4. 3의 제곱수를 3으로 나누고 n을 갱신한다.

5. 위 과정을 n이 0이 될 때까지 반복한다. (아래 코드에서는 나타낼 수 있는 3진법의 자리수 만큼 반복했다.)

 

#include "bits/stdc++.h"

using namespace std;

unsigned long long solution(int n) {
    unsigned long long answer = 0;
    
    int sq = 0;    
    int npow = 0;
    
    while(npow <= n)
        npow = pow(3,sq++);
        
    npow /= 3;
    sq--;
     
    int nNum = n;   
    vector<int> vec;

    if(sq < 0)
        vec.push_back(n);
    
    for(int i = sq ; i > 0 ; i--)
    {
        int nCnt = 0;
        int tmp = nNum - npow;

        if(tmp <= 0)
        {
            if(tmp == 0)
            {
                nCnt++;
                nNum = tmp;
            }
            
            vec.push_back(nCnt);
            npow /= 3;
            continue;
        }

        
        nCnt++; 
        
        if(tmp >= npow)
        {          
            tmp -= npow;
            nCnt++;                       
        }
          
        nNum = tmp;
        vec.push_back(nCnt);
        npow /= 3;
        
            
    }
    
    for(int i = 0 ; i < vec.size() ; i++)  
    {
        
        answer += vec[i] * pow(3,i);
    }
    
    
    
    return answer;
}

---

다른 정답

 

주어진 정수를 3으로 나눈 나머지를 계속 넣으면 3진수를 뒤집은 수가 된다.

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<int> v;
    while(n > 0){
        v.push_back(n%3);
        n/=3;
    }
    int k = 1;
    while(!v.empty()) {
        answer += k*v.back();
        v.pop_back();
        k*=3;
    }

    return answer;
}