[ 프로그래머스 124 나라의 숫자 (Lv2) ] (C++)

프로그래머스의 124나라의 숫자(Lv2) 문제이다.

 

[ 문제풀이 ]

프로그래머스의 124나라의 숫자 문제이다.

모든 수를 표현할 때, 1, 2, 4 만 사용할 때 주어진 숫자를 124나라의 숫자로 바꾸면 어떤 숫자가 나오는지 구해야 하는 문제이다.

 

딱 보자마자, "3개의 숫자를 사용" 한다는 점에서 "3진수"를 쉽게 떠올릴 수 있을 것이다.

본인도 3진수를 쉽게 떠올렸지만, 정말 예상치 못한 부분에 걸려서 시간이 조금 걸렸던 문제이다.

지금부터 2개의 나라를 비교할 것이다.

하나는 모든 수를 표현할 때, '0', '1', '2'만 사용하는 120 나라와 '1', '2' ,'4'만 사용하는 124나라를 비교할 것이다.

위의 표는 1 ~ 9까지의 숫자를 각 나라의 진법으로 표시해본 숫자들이다.

두 나라 모두 3개의 숫자만으로 숫자를 표현한다는 점에서 대부분의 숫자들의 결과가 같다는 것을 알 수 있다.

하지만 ! 빨강색으로 표시해놓은 숫자 '3', '6', '9'를 살펴보자.

정말 이상하게도 빨강색으로 표시해놓은 숫자들만이 결과가 다르다는 것을 알 수 있다.

왜 빨강색으로 쓴 숫자들만 결과가 다를까 ?? 다른 숫자들과는 무슨 차이가 있을까 ??

먼저, 빨강색으로 표시된 숫자들은 모두 "3으로 나누어 떨어지는 숫자" 라는 공통점을 가지고 있다.

그렇다면, "3으로 나누어 떨어지는 숫자" 들만 왜 결과가 다를까 ??

120나라, 즉, 일반적인 3진수를 한번 생각을 해보자.

3으로 나누어 떨어지는 어떤 숫자 'A'가 있다고 가정을 해보자. 이 숫자를 3진수로 표현했을 때, 가장 마지막 자리는 0, 1, 2 중에 무슨 숫자가 올까 ?? 바로 무조건 '0'이 오게 될 것이다.

A = 3 이라고 가정해보자. 3을 3진수로 표현하게되면, "10" 으로 가장 마지막 자리는 '0'이 오게 된다.

A = 6 이라고 가정해보자. 6을 3진수로 표현하게되면, "20" 으로 가장 마지막 자리는 '0'이 오게 된다.

A = 9 라고 가정해보자. 9를 3진수로 표현하게되면, "100" 으로 가장 마지막 자리는 '0'이 오게 된다.

즉 ! 3으로 나누어 떨어지는 어떤 수 A를 3진수로 표현을 해본다면, 그 마지막 자리는 반드시 0이 오게 될 것이다.

반드시 0이 온다는 것은 어떻게 자명하게 할 수 있을까 ?? 가장 마지막 자리는 0 , 1 , 2 중에 하나의 값을 가지게 된다. 숫자 '7'을 예로한번 들어보자. 7을 3진수로 나타내보면 "21"이 될 것이고, 이 3진수로 표현된 "21"을 다시 7로 바꾸는 과정은 다음과 같이 계산할 수가 있다.

( 2 * (3^1) ) + ( 1 * (3^0) )

즉 ! 마지막 자리는 3^0의 크기를 가지는 친구로써, 그 자리에 오는 숫자가 1이라면 + 1을, 2라면 + 2를, 0이라면 + 0을 더해주는 역할을 하게 된다.

3의 배수인 어떤 숫자에다가 1혹은 2를 더했을 때 이 숫자가 3으로 나누어 떨어질 수 있을까? 라고 생각을 해볼 수 있다.

절대 그럴 수가 없다. 따라서, 3의 배수는 가장 마지막 자리가 0이 될 수 밖에 없다.

 

다시 본론으로 돌아와보자.

120나라와 124나라에서 가장 큰 차이점을 보인 숫자들은 "3으로 나누어 떨어지는 숫자들" 이였다.

그렇다면, 왜 차이점이 생기게 되는 것일까 ??

바로, "124"나라에서는 숫자 '0'을 사용하지 않기 때문이다. 숫자 '0' 대신 '4'를 사용하는 꼴이기 때문이다.

그렇기 때문에 120나라에서 0을 가지는 숫자들은 124나라와 차이점이 생기는 것이다.

 

그럼 이를 어떻게 맞춰줄 수 있을까 ??

주어진 10진수를 124나라의 진수법으로 변환을 할 때, 3으로 나누어 떨어진다면 그 몫을 하나 낮추어서 나머지가 3이 되도록 만들어주는 것이다. 숫자 '6'을 한번 예로 들어보자. 6을 3으로 나누게 되면 몫이 '2'이고 나머지가 0이 되는 것이 올바른 계산이다. 그런데 ! 몫을 하나 낮추어서 계산을 해보면 몫이 1이되고, 나머지가 3이 되는 형태가 발생한다.

나머지가 3이 되었다는 것은, 정상적으로 계산을 했으면 나누어 떨어졌다는 것을 의미하고 나머지가 0이 나왔음을 의미하기 때문에, '0' 대신에 '4'를 적어주면 된다.

 

이를 간단하게 계산을 한다면, "3으로 나누어 떨어진다면, 나머지를 0 대신 4로 적어주고, 몫을 하나 감소시킨 후, 계산을 진행" 한다고 볼 수 있다. 예시 몇가지를 살펴보자.

 

숫자 '3'을 한번 살펴보자.

3을 3으로 나누게 되면 몫이 1이 되고 나머지가 0이 된다. 단 ! 124나라에서는 '0'대신 '4'를 사용하는 꼴이기 때문에, 나머지가 "4"가 될 것이다.

그런데 ! 여기서 나누어 떨어졌으니까 몫을 하나 낮춰보자. 그럼 몫이 0이 될 것이고, 나눠질 숫자가 0이 되었으므로 더 이상의 계산없이 "4"로 계산이 끝나게 된다.

 

숫자 '5'를 한번 살펴보자.

5를 3으로 나누게 되면 몫이 1이되고 나머지가 2가 된다. 나머지로 "2"를 적어주자.

여기서는 나누어 떨어지지 않았으므로 몫을 가지고 그대로 계산을 해보자.

몫인 1을 3으로 나누게 되면 몫이 0이되고 나머지가 1이 된다. 나머지를 추가해주면 "12"로 124나라의 '5'를 "12"가 된다.

 

숫자 '9'를 한번 살펴보자.

9를 3으로 나누게 되면 몫이 3이 되고 나머지가 0이 된다. 나머지가 '0'이므로 '0'대신 "4"를 적어주자.

그런데 여기서 나누어 떨어졌으므로, 몫을 하나 감소시켜주자. 몫이 "2"가 될 것이다.

2를 3으로 나누게 되면 몫이 0이되고 나머지가 "2"가 되므로 '9'는 124나라의 "24"가 된다.

 

[ 소스코드 ]

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
string Str[] = { "4" , "1" , "2" };
 
string solution(int n) 
{
    string answer = "";
    while(n > 0)
    {
        answer += Str[n % 3];
        if(n % 3 == 0) n = (n / 3) - 1;
        else n = n / 3;
    }
    reverse(answer.begin(), answer.end());
    return answer;
}