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

문제 설명

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

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

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

제한사항

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

---

풀이

35분
3진법으로 코드를 처음에 구성하였는데, 3의 배수인 경우에 반례가 발생했다. 이유를 고민하다가 꽤 긴 시간을 허비했는데, 결국 손으로 직접 계산을 반복하는 과정에서 3의 배수일 경우 몫에서 1을 빼주어야 함을 깨닫고 풀이할 수 있었다. 0을 사용하지 않으므로 나누어 떨어졌을 때 해당 숫자를 표시할 수 없기 때문이었는데, 결과를 알고나니 이유가 보이게 되었다.

코드

// 04:04~ 04:40
#include <string>
#include <vector>

using namespace std;

string solution(int n) {
    string answer = "";
    char digit;
    while(n > 0){
        if(n % 3 == 0) digit = '4';
        else digit = n % 3 + '0';
        answer.insert(answer.begin(), digit);
        n /= 3;
        if(digit == '4') --n;
    }
    return answer;
}