programmers12899

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이하의 자연수 입니다.

입출력 예

numbers	result
1	1
2	2
3	4
4	11

//11: 42, 12: 44, 13: 111, 14: 112, 15: 114, 16: 121 ...
// 1 나누기 3 = 0 나머지 1
// 2 나누기 3 = 0 나머지 2
// 3 나누기 3 = 1 나머지 0 index?

function solution(n) {
    var answer = '';
    console.log(answer)
    let fourOneTwo = [4, 1, 2]
    if (n == 3) return '4'

    let aux = (n) => {
        if (n == 0) {
            return answer
        }
        answer = fourOneTwo[n % 3] + answer
        aux(Math.floor(n / 3))

    }
    aux(n)
    return answer
}

정확성 테스트는 풀렸는데, 효율성 테스트를 전부 통과하지 못했다.
n이 5억개일 경우, 이를 반복하는 경우의 수가 많아져서 문제가 된다고 예상한다. 1억개도 많다. 계산을 더 줄여야 한다.

function solution2(n) {
    var answer = ''; 
    //console.log(answer)
    let fourOneTwo = [4, 1, 2]

    let aux = (n) => {
        if (n == 0) {
            return
        }
        answer = fourOneTwo[n % 3] + answer
        if (Math.floor(n % 3 === 0)) {
            aux(Math.floor(n / 3) - 1)
        } else {
            aux(Math.floor(n / 3))
        }
    }
    aux(n)

    return answer
}

3/3일 때 몫인 1이 발생하여 계산이 한번 더 되는 문제를 찾았다.
n=3이면 answer는 '4'가 나와야 하는데 '14'가 나타나게 된다.

n%3이 0일 경우, n/3의 몫에서 -1을 빼서 계산한다면 불필요한 계산과정이 일어나지 않는다. n=3일때 answer는 '4'가 되고, (n/3-1)값을 재귀하여 base case인 if문에서 멈추게 한다.

유효성 문제를 통과하지 못한 이유
중간에 console.log(answer)때문에 계산시간이 길어진 탓이다.
실제로 5억을 3으로 나누는 횟수를 count하면 700번 아래로 나타난다. 시간복잡도가 그리 크지 않다는 말이다.

let divCounter = (num) => {
    let i = 0;
    let iNum = num;
    while (iNum > 0) {
        i++;
        iNum = iNum / 3;
    }
    return i;
}
let maxCase = 500000000;
console.log(divCounter(maxCase)) => 697이 나타난다.
*/