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

문제

 

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

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

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

10진법  124 나라  10진법  124 나라

1	1	6	14
2	2	7	21
3	4	8	22
4	11	9	24
5	12	10	41

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

제한사항

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

---

입출력 예

n     result

1	1
2	2
3	4
4	11

 

---

해설

기본적으로 3진법과 124나라의 차이점은 3진법에서 10을 124나라에선 4라고 표현하는 데 있다.
즉, 3진법으로 먼저 바꾸고, 각 자리의 숫자를 탐색하면서 0을 만났을 때, 그 앞 자리의 숫자를 -1해주는 방식으로 문제를 해결 할 수 있다.

n은 arr배열 마지막에서부터 0으로 탐색
arr[n] == 0?
no -> n--;
yes -> arr[n] = 4; arr[n - 1] == 1, 2, 0? ... ㉠
         arr[n - 1] == 1, 2 -> arr[n - 1]--; ... ㉡
         arr[n - 1] == 0 -> arr[n - 1]에 대해서 ㉠을 반복 적용

이 때, 다시 return하고 arr[n - 1]--를 하는 과정에서 arr[n - 1]이 4일 경우가 있기 때문에, 해당 경우에는 
arr[n - 1] == 4 -> arr[n - 1] = 2
이런 식으로 if문을 한 번 더 삽입하여 문제를 해결해야 한다. 
이 부분을 처음 문제를 해결할 때, 놓쳐서 계속 빙빙 돌았었다.

이를 코드로 나타내면 다음과 같다.

function solution(n) {
    var arr = n.toString(3).split('');
    for(var i = arr.length - 1; i >= 0; i--){
        if(arr[i] == '0'){
            if(i != 0) make0to4(arr, i);
        }
    }
    var answer = '';
    answer = Number(arr.join('')).toString(); // 맨 앞이 0인 경우, 0을 없애고 다시 String으로 변환
    return answer;
}

function make0to4(arr, n){
    arr[n] = 4;
    if(arr[n - 1] == 0){
        make0to4(arr, n - 1);
    };
    if(arr[n - 1] == 4) arr[n - 1] = 2;
    else 
        arr[n - 1]--;
    return;   
}

 

느낀 점

• 다른 사람의 풀이를 봤더니, 정말로 간단하고 아름답게 문제를 해결하고 있었다. 내 식과 비교해보니, 나는 진법의 변환 공식이랄까 규칙을 몰랐었다. 이에 대해 알아보니 아래와 같은 방식으로 변환하는 방법을 설명할 수 있었다.

A 진법 ⇒ 10 진법 변환의 재귀 관계 : '앞자리 수' × 진법 + '마지막 자리 숫자' - 예) 2진법 수
10 진법 ⇒ B 진법 변환의 재귀 관계 : '앞자리 수' 출력 후, '마지막 자리 숫자' 출력

지식 in 예시를 통해 정확한 설명을 들을 수 있다.