[JS] 124 나라의 숫자

문제

처음 풀이 (오답 -> 시간초과)

function solution(n) {
    const num = {1: '1', 2: '2', 3: '4'};
    const queue = ['1', '2', '4'];
    const rules = ['4', '1', '2'];
    let count = 4;
    let prefix = 0;
    
    while (count <= n) {
        const idx = count % 3;
        num[count] = queue[prefix] + rules[idx];
        queue.push(num[count]);
        count++;
        if (idx === 0) {
            prefix += 1;
        };
    }
    
    return num[n];
}

문제를 충실하게 구현해서 1부터 n가지 모든 3진법 수를 구했습니다. 하지만 생각해보니 진법을 구하는건 기존 n에서 원하는 진법의 숫자로 나누면 되는 것을 망각했습니다. 예를 들어서 2진법으로 나타내고 싶으면 간단하게 n에서 2로 계속 나누면 되는거죠.

정답 풀이

10진법	124 나라	10진법	124 나라
1	1	6	14
2	2	7	21
3	4	8	22
4	11	9	24
5	12	10	41

여기서 10진법을 3으로 나누었을 때를 보면,

• 나머지가 1일 경우 124에서 1
• 나머지가 2일 경우 124에서 2
• 나머지가 0일 경우 124에서 4

이라는 것을 알 수 있습니다.

먼저 8이라는 숫자를 124 나라의 숫자로 변환하는 과정을 생각해봅시다.

1. 8 % 3 = 2 이므로 나머지가 2일 경우 2가 나오게 출력해야합니다.
2. 8 / 3 = 2.xx이지만 우리는 몫만 필요하므로 (3 * 2 + 2의 형태가 필요합니다.) 몫만 입력
3. 2 % 3 = 2 이므로 2가 나오게 출력해서 22가 되는 것을 알 수 있습니다.

이를 코드로 구현하면 다음과 같습니다.

    var answer = '';
    const rules = [4, 1, 2];
    
    while (n > 0) {
        answer = rules[n % 3] + answer;
        n = parseInt(n / 3);
    }

하지만 문제가 생깁니다. 3일 경우 정답은 4가 되어야 하는데 코드에서는 '14'가 되어버리는거죠.
왜 이런일이 생겼을까요?
이유는 n이 3의 배수일 때, 몫이 생겨버리기 때문입니다. 예를들어서 9일 경우 우리는 (3 2 + 3)의 형태가 필요하지만 그냥 3으로 나누면 (3 3)이라서 우리가 원하는 형태를 얻을 수 없습니다. 이는 n에 -1을 해주면 간단하게 해결됩니다. [4, 1, 2]가 같은 몫으로 계산할 수 있게 됩니다.

결론적으로는 그냥 n%3을 하면 결과가 1,2,3이기 때문에, index로 사용이 어렵기 때문입니다.

function solution(n) {
    var answer = '';
    const rules = [4, 1, 2];
    
    while (n > 0) {
        answer = rules[n % 3] + answer;
        n = parseInt((n-1) / 3);
    }
    
    return answer;
}

그래서 최종 정답코드는 위와 같습니다.