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

진법 계산에 대한 명확한 이해가 있으면 어렵지 않은 문제입니다만 진법 계산이 뭔가 아리까리한 상황이라면 생각보다 어렵게 느껴질 수도 있어요. 초등학교 때 10진수를 다른 진수로 변환할 때 쓰는 방법이 있었습니다. 21이라는 10진수를 2진수로 바꾸려면 다음과 같이 하면 됩니다.

1. 21을 2로 나눈 나머지..........1

2. 21을 2로 나눈 몫 -> 10

3. 10을 2로 나눈 나머지..........0

4. 10을 2로 나눈 몫 -> 5

5. 5를 2로 나눈 나머지............1

6. 5를 2로 나눈 몫 -> 2

7. 2를 2로 나눈 나머지............0

8. 2를 2로 나눈 몫....................1

10진수는 0~9를 표현하듯이 2진수는 0~1로 표현합니다. 2진수이므로 2가 제수가 되어 피제수를 2보다 작아질 때까지 나눠주면 됩니다. 나머지 값이 각 자리를 차지하게 됩니다. 나눌수록 자릿수가 올라가는 것이므로 마지막에 나온 값이 가장 높은 자릿수가 됩니다. 즉 10101(2)이 10진수 21의 2진수입니다. 검증을 해보면 2^0*1 + 2^1*0 + 2^2*1 + 2^3*0 + 2^4*1 = 1 + 4 + 16 = 21입니다.

 

124 나라의 숫자

문제설명

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

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

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

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

 

제한사항

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

 

풀이

1, 2, 4 세 개의 숫자만 사용하기 때문에 기본적으로 3진법이 적용됩니다. 일반적인 3진법은 10진수 3을 10으로 표현하겠지만 여기에선 3을 4로 표현합니다. 3진법이므로 3을 이용해 나머지를 구하고 그다음 연산은 3으로 나눈 몫으로 진행하면 되는데요. 7을 예로 들어보겠습니다. 7의 3나머지 연산은 1입니다. 첫 번째 자릿수가 1이 됩니다. 그다음 연산은 몫인 2로 하면 됩니다. 2는 똑같이 2네요. 그래서 21이 나옵니다. 3의 배수는 자세히 보면 나머지가 0이면 4를 표기하는데 그다음 연산 때 3으로 나눈 뒤 빼기 1을 하는 형태입니다. 3, 6, 9 전부 그래요. 이를 코드로만 옮기면 됩니다.

#include <string>
#include <vector>

using namespace std;

string solution(int n) {
  string answer = "";
    while (n)
    {
        if (n % 3)
        {
            int a = n % 3;
            answer.insert(0, to_string(a));
            n /= 3;
        }
        else
        {
            answer.insert(0, "4");
            n = n / 3 - 1;
        }
    }
    return answer;
}