[c++][프로그래머스] 124 나라의 숫자

https://programmers.co.kr/learn/courses/30/lessons/12899

코딩테스트 연습 - 124 나라의 숫자

124나라의 숫자는 1,2,4로만 이루어져 있습니다.

 

3진법으로 계산한다고 생각하고 풀었는데, 0이 존재하지 않아서 많이 헷갈렸던 문제입니다.

 

3, 3+9, 3+9+27 ... 의 방법으로 더해가면서 풀었더니 풀렸습니다.

 

44가 12번째 숫자라는 사실을 알고 난 후에 전체 n 값에서 제거해가면서 문제를 풀었습니다.

#include <string>
#include <vector>

using namespace std;

string solution(int n) {
    string answer = "";
    
    int div = 1;        // 자리수를 나타냄
    vector<int> count;  // 자리수 카운트 벡터
    
    while(n >= div)
    {
        n -= div;
        count.push_back(1);
        div *= 3;               // 3씩 곱해가면서 자리수를 넣음
    }
    
    int index = count.size() - 1;    // count 벡터의 index를 위해
    div /= 3;
    
    while(n>0)
    {
        if(n >= div)
        {
            n -= div;
            count[index]++;         // 나누면서 카운트의 인덱스를 증가시킴
        }
        else
        {
            div /= 3;               // 내려가면서
            index--;
        }
    }
    
    for(int i=count.size()-1; i>= 0 ; i--)
    {
        if(count[i] == 1)
        {
            answer += '1';
        }
        else if(count[i] == 2)
        {
            answer += '2';
        }
        else if(count[i] == 3)
        {
            answer += '4';
        }
    }
    
    return answer;
}