[프로그래머스] 124 나라의 숫자 - Lv.2 / Javascript

https://programmers.co.kr/learn/courses/30/lessons/12899

코딩테스트 연습 - 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 함수를 완성해 주세요.

 

문제 해결 아이디어

숫자만 1, 2, 4일 뿐이지 0, 1, 2을 사용하는 3진법의 개념과 같다. 즉, 3으로 계속 나눠서 몫이 0이 될 때까지 나머지를 1, 2, 4로 기록해 주면 된다.

반복문을 사용하는 방법과 재귀를 사용하는 방법이 있을 것인데, 나는 재귀를 사용했다.

종료 조건은 몫이 0일 때고, 그 조건이 될 때까지 몫을 3으로 나눠서 재귀를 돌아 준다.

여기서 체크해 주어야 할 규칙은 3으로 딱 나누어 떨어지는 수일 때다.

예를 들어 3이라면 몫이 1, 나머지가 0이기 때문에 일반적인 3진법으로 표현하면 10이다. 하지만 124 나라에서는 자연수만 존재하므로 1부터 시작이기 때문에 실제로는 4가 된다.

15라면 몫이 5, 나머지가 0 -> 몫인 5를 한 번 더 3으로 나누면 몫이 1, 나머지가 2라서 일반적인 3진법으로는 120인데 124 나라에서는 114이다.

즉, 공통된 규칙이 나머지가 0인 3으로 나누어 떨어지는 수일 때는 다음에 넘겨 줄 때, 즉 몫을 또 한번 3으로 나누어 넘겨 주는 재귀를 돌 때 몫에서 -1을 하고, 나머지를 0이 아닌 4로 기입해 주어야 한다는 것이다.

따라서 나머지를 담아 두는 배열 let arr = [4, 1, 2]를 만들어 둔 다음에 현재 수(몫)에 대한 나머지를 계속해서 answer 앞에 붙이고, 3으로 나누어 떨어지는 경우 몫에서 -1을 해 재귀를 돌고, 아닌 경우 몫으로 돌려 주면 되겠다.

 

 

완성된 코드

let answer = '';
let arr = [4, 1, 2];

function solution(n) {    
    // 3진법이라고 생각
    // 10진법 3 -> 3으로 나누면 몫이 1, 나머지가 0 -> 3진법 10 (124나라 4)
    // 10진법 15 -> 3으로 나누면 몫이 5, 나머지가 0 -> 10진법 5를 3으로 나누면 몫이 1, 나머지가 2 -> 3진법 120
    // 공통된 규칙: 나머지가 0이면 몫에서 -1, 나머지를 4로

    solve(n);
    
    return answer;
} 


const solve = (n) => {
    if (n === 0) {
        return;
    }
    // 나머지를 앞으로 계속해서 붙여준다. 나머지가 0이면 4, 1이면 1, 2이면 2
    answer = arr[n % 3] + answer;
    // 나머지가 0이면 몫은 -1
    n % 3 === 0 ? solve(parseInt(n / 3) - 1) : solve(parseInt(n / 3));
}