[프로그래머스] 124나라 - C++

문제 설명

124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다.

1. 124 나라에는 자연수만 존재합니다.
2. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다.

예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다.

10진법                           124 나라                                      10진법                                        124 나라

1	1	6	14
2	2	7	21
3	4	8	22
4	11	9	24
5	12	10	41

자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요.

제한사항

• n은 500,000,000이하의 자연수 입니다

---

     기본적으로 1 ,2 ,4로 숫자를 나타내므로 삼진법과 같은 개념으로 숫자를 3으로 나눈 나머지로 숫자의 뒷부분부터 채워 나간다고 생각할 수 있다.  삼 진법은 0-> 0 1->1 2->2 3->10 4->11과 같은 규칙으로 숫자가 정해지는데 이는 3으로 나눈 나머지를 뒤에서부터 채운 형식이다.

    이를 0 1 2 로 생각하지 않고 1 2 4로 치환해주면 124 나라의 숫자가 된다. 하지만 여기서 유의할 점은 삼진법은 0에서 시작하지만 위 문제는 1부터 숫자가 시작된다. 따라서 [ 1 2 3 ]을 [ 0 1 2 ]로 바꾸어 생각하고 [1 2 4]로 다시 한번 바꾸어주면 124 나라의 숫자가 된다. 따라서 (n-1)%3을 저장하고 다음 n을 n/3 이 아닌 (n-1)/3으로 [ 0 1 2 ]로 이루어진 숫자 배열을 구하고 마지막에 [ 0 1 2 ]를 [ 1 2 4 ]로 바꿔주면 정답을 구할 수 있다.

#include <string>
#include <vector>
#include <stack>
using namespace std;

string solution(int n) {
    string answer = "";
    stack <int> s;
    int a;
    while(n > 0){
        s.push((n-1)%3);
        n = (n-1)/3;
    }
    while(!s.empty()){
        a = s.top();s.pop();
        switch(a){
            case 0 :
                answer += "1";
                break;
            case 1 :
                answer += "2";
                break;
            case 2 :
                answer += "4";
                break;
        }
    }
    return answer;
}

---

    문제를 보자마자 진법 문제라는 것을 쉽게 알 수 있었다. 그래서 n%3 과 n/3으로 문제를 풀었는데 원하는 답이 나오지 않았다. 조금 더 생각하니 숫자가 1부터 시작하여 (n-1)%3으로 바꾸어 주었으나 역시 원하는 답이 나오지 않았다. 그래서 적으면서 풀 겸 애플 펜슬을 충전시켜 놓고 다른 시도도 해볼 겸 n = (n-1)/3으로 바꾸니 정답이 나왔다. 다른 블로그들을 보니 4 1 2의 순서로 3으로 나누어 떨어지면 -1을 하는 방식으로 풀고 추가적으로 좋아요를 많이 받은 코드라고 이 방식을 올려놨던데 그 방법에 대해 설명해 놓은 블로그를 찾기 힘들었다. 이번 포스팅을 적으면서 그 원리에 대해 더 생각해본 것 같다.