[프로그래머스 Lv.2] 124 나라의 숫자

문제 링크: Lv.2 124 나라의 숫자

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

 

나만 Lv.2라고 안 느껴졌을까...? 처음에 설명 듣고 아아~ 하다가 풀다보니까 생각보다 더 어려웠다. 풀이를 보고서도 아리송한 부분이 남아있는데, 진법 개념이 덜 잡힌 것 같다.생각해보니까, 진법의 변환 과정을 이용하지만, 진법 문제는 아니다.

 

어떤 자연수를 2진법으로 변환하는 과정을 미리 생각해두자.

14 = 2^3 * 1 + 2^2 * 1 + 2^1 * 1 + 2^0 * 0

우변의 각 항을 base^exp * coef라 표현할 때, coef는 0 또는 coef < base인 자연수이다. 당연하게도, coef가 base가 되어버리면 이는 한 자리 위로 올라가버리기 때문이다.

 

이걸 기억하고 문제의 내용으로 돌아오자.

 

1, 2, 4로 하면 헷갈리니까 124 나라가 아니라 2378 나라의 숫자를 만든다고 생각하자. 10진법으로 19는, 2378 나라에서는 87로 표현된다. coef가 1, 2, 3, 4일 때 각각 2, 3, 7, 8로 대응된다는 점을 생각하면 다음과 같은 결과가 나와야 한다.

19 = 4^1 * 4 + 4^0 * 3

그런데 4진법처럼 계산해보면 실제로는 다음과 같은 결과가 나온다.

19 = 4^2 * 1 + 4^1 * 0 + 4^0 * 3

coef가 0이 없고 coef <= base이기에 이러한 차이가 발생한다. 그렇기에 나누었을 때 나머지가 0이 나오면, 몫에서 1을 빼주고, 나머지는 가장 큰 숫자인 8로 바꾸어준다. 즉, 19에 대해서는 다음과 같은 과정이 이루어진다.

19 = 4^2 * 0 + 4^1 * 4 + 4^0 * 3

0이 없기에, 몫에서 1을 빼줌으로써 4^2 하나를 나머지에게 넘겨주게 되고, 나머지는 그 4^2를 갖기에 coef를 n으로 올려주는 것이다.

 

#include <string>
#include <vector>

using namespace std;

string solution(int n) {
    vector<int> arr;
    
    while (n > 0) {
        int mod = n % 3;
        n /= 3;
        if (mod) {
            arr.push_back(mod);
        } else {
            arr.push_back(4);
            n--;
        }
    }
    
    string answer = "";
    for (int i = arr.size() - 1; i >= 0; i--) {
        switch(arr[i]) {
            case 1: answer += '1'; break;
            case 2: answer += '2'; break;
            case 4: answer += '4'; break;
        }
    }
    
    return answer;
}