프로그래머스 - 124 나라의 숫자(c++)

문제 설명

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

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

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

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

 

제한사항

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

 

입출력 예

 

규칙 찾기

10진법 숫자 1~20을 124 나라 숫자로 바꿔보면 아래 표처럼 나타낼 수 있다.

1	1	6	14	11	42	16	121	...
2	2	7	21	12	44	17	122
3	4	8	22	13	111	18	124
4	11	9	24	14	112	19	141
5	12	10	41	15	114	20	142

 

124 나라 숫자의 규칙을 살펴보면 눈에 띄는 점들이 있다.

 

1.  끝 자리 규칙

10진수를 3으로 나눈 나머지가 0 이면 -> 124 나라 숫자의 끝자리는 4

10진수를 3으로 나눈 나머지가 1 이면 -> 124 나라 숫자의 끝자리는 1

10진수를 3으로 나눈 나머지가 2 이면 -> 124 나라 숫자의 끝자리는 2

 

2. 3제곱 규칙

124 나라 숫자의 자릿수가 1개 증가할 때, 10진수의 범위는 3 제곱으로 증가한다.

ex)

10진수 1~3 (3*1) -> 124 나라의 숫자에서는 1자리  

10진수 4~12 (3*3)-> 124 나라의 숫자에서는 2자리 

10진수 13~39 (3*3*3)> 124 나라의 숫자에서는 3자리

....

 

->> 124 나라 숫자가 3개 이기 때문에 각 자리수에 해당하는 경우의 수가 3가지씩이기 때문!

 

 

위 2가지 규칙으로 도출해낸 풀이 방법

1. 주어진 자연수 n을 3으로 나눠 나머지를 구한다. (n>0)

2. 위에서 구한 나머지로 124 나라 숫자의 끝자리를 구해서 앞에 더한다. (끝 자리 규칙)

3. n의 값을 (n-1)/3으로 대체한 후 위 과정을 되풀이 한다. (3제곱 규칙)

* n에 -1을 한 이유는 이전 자리의 10진수 범위안에 들도록하기 위함

   ex) 10진수 39의 경우, 그대로 3으로 나누면 13이므로 x

 

 

풀이

#include <string>
#include <iostream>
using namespace std;

string solution(int n) {
    string answer = "";
    char end[3] = {'4','1','2'};
    
    while(n>0){
        int r = n%3; // 1. 주어진 자연수 n을 3으로 나눠 나머지를 구한다. (n>0)
        answer = end[r] + answer; //위에서 구한 나머지로 124 나라 숫자의 끝자리를 구해서 앞에 더한다. (끝 자리 규칙)
        n = (n-1)/3;   // n의 값을 (n-1)/3으로 대체한 후 위 과정을 되풀이 한다. (3제곱 규칙)
    }
    
    cout << n;
    return answer;
}

 

 

 

코딩테스트 연습 - 124 나라의 숫자