[프로그래머스 lv2] 124나라의 숫자 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

모든 숫자를 (1, 2, 4) 3가지 수로 나타낸다고 했으므로 3진법과 관련있음을 유추할 수 있다.

 

10진법을 3진법으로 나타내기 위해서는 3으로 계속 나누어가며 나머지가 무엇인지 살펴야 한다.

나머지가 1일 떄는 1, 나머지가 2일 때는 2, 나머지가 0일 떄는 4를 문자열에 붙이고 맨 마지막에 이를 뒤집어 결과를 리턴한다.

 

단 주의할 것은, 3으로 나누어떨어질 경우(나머지가 0일 경우) 몫을 1 감소시키고 나머지를 3 증가시켜 3을 4로 변환시키자.

 

예를 들어, 10을 1, 2, 4 숫자로 변환할 때

10 / 3 = 몫 3 ... 나머지 1 => 1

3 / 3 = 몫 1 ... 나머지 0 => 몫에 1을 뺴주면 나머지는 3이 된다. 나머지 3을 4로 변환하여 문자열에 붙인다.

결과적으로, 10은 41로 변환된다.

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

string solution(int n) {
    
    string s = "";
    while (n) {
        int d = n%3;
        n /= 3;
        if (d == 1) s += "1";
        else if (d == 2) s += "2";
        else { // d == 0
            s += "4";
            n--;   
        }
    }
    reverse(s.begin(), s.end());
    return s;
}