[Programmers] 124 나라의 숫자

🔒 문제

💡 생각의 흐름

1,2,4 3개의 숫자만으로 한 자리씩 표현

총 자릿수는 3^N + 3^N-1 + 3^N-2 .... 3^0 => N+1 의 문자열 길이를 갖는다.

군 내에서 N번째 숫자를 3^N * n + 3^N-1 * n ... 

N+1 만큼 loop을 돌고 n을 이어붙이면 된다고 생각했다.

 

먼저, 10진수 -> 124나라의 숫자가 바로 생각나지 않으니 
124나라의 숫자 -> 10진수변환을 곱씹어 보았다. 
예를들면 10진수 '241'
3^2 * 2 + 3^1 * 4 + 3^0 * 1

---

>[0단계] 
3마다 단위가 바뀌는 걸로 봐서 3진법!!!!!?!?!?! 근데 숫자 0과 4를 따로 처리해야겠네?
[1단계]
124나라의 숫자의 길이 == 3^1 + 3^2 + 3^3 + .... 3의 제곱수의 누적합이 더 커지는 단계이다.
예를 들면 '20'이라는 10진수는 3 + 9 + (27) 에서 3+9 까지의 합보다 크고 27보다 작으므로 3자리.
[2단계]
1단계에서 구한 길이를 length 라고 하면 3^length-1 * N + 3^length-2 * M + ... 3^0 * K
뒤에 곱해진 수 NM...K 가 곧 124나라의 숫자이다.

 

😅 실수

3진법 0, 1, 2를 {1, 2, 4}로 대치한 것이 잘못.

ex) 6=>  3^1 * 1 + 3^0 * 3 == 3^1 * 2  (3진법이지만 * 3을 허용.)>[0단계] 
3마다 단위가 바뀌는 걸로 봐서 3진법!!!!!?!?!?! 근데 숫자 0과 4를 따로 처리해야겠네?
[1단계]
124나라의 숫자의 길이 == 3^1 + 3^2 + 3^3 + .... 3의 제곱수의 누적합이 더 커지는 단계이다.
예를 들면 '20'이라는 10진수는 3 + 9 + (27) 에서 3+9 까지의 합보다 크고 27보다 작으므로 3자리.
[2단계]
1단계에서 구한 길이를 length 라고 하면 3^length-1 * N + 3^length-2 * M + ... 3^0 * K
뒤에 곱해진 수 NM...K 가 곧 124나라의 숫자이다.

 

🔑풀이

import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    static int totalSum = 0, length = 0;

    // 3진법과 유사하나 0이란 숫자가 존재하지 않으므로 모든 자리수마다 1 이상의 숫자를 남김
    // -> 결국 totalSum + 1 의 자리를 MSB부터 내려가면서 매번 남겨야함 (ex 1, 4, 12, 39...)
    static ArrayList<Integer> positionTotalSum = new ArrayList<Integer>(Arrays.asList(0, 1));

    // 1단계 124나라 숫자 길이 구하기, length 에 124나라 숫자 길이가 초기화됨.
    static void getNumberOfDigit(int number) {
        do {
            totalSum += Math.pow(3, ++length);
            positionTotalSum.add(totalSum + 1);
        } while (number > totalSum);
    }

    public String solution(int n) {
        //        자릿수 결정 -> length 구해짐
        getNumberOfDigit(n);

        var stringBuilder = new StringBuilder();

        // 2단계 MSB 부터 구하기
        for (int m = length - 1; m >= 0 ; m--) {
            var powerOfThree = (int) Math.pow(3, m);
            int quotient = (int) (n / powerOfThree);
            int remainder = (int) (n % powerOfThree);
            // 남은 자리수에 1이 올 수 있는지 검사
            if (remainder >= positionTotalSum.get(m)) {
                n = remainder;
            } else {
                quotient--;
                n = remainder + powerOfThree;
            }
            if ((quotient == 3)) stringBuilder.append(4);
            else stringBuilder.append(quotient);
        }
        return stringBuilder.toString();
    }
}