[프로그래머스] 12899. 124 나라의 숫자 풀이

#Problem

12899. 124 나라의 숫자

#Approach

분명 3진법 같은데, 약간의 tweak**이 필요해서 푸는데 오래 걸렸다.
숫자를 계속 써보면서, LSB부터 하나씩 구한다는 발상으로 접근했다.

우선, LSB는 1, 2, 4가 계속 반복된다.

| n | 124나라 | | 1 | _ _ _ _ 1 | | 2 | _ _ _ _ 2 | | 3 | _ _ _ _ 4 | | 4 | _ _ _ 1 1 | | 5 | _ _ _ 1 2 | | 6 | _ _ _ 1 4 | | 7 | _ _ _ 2 1 | | 8 | _ _ _ 2 2 | | 9 | _ _ _ 2 4 | | 10 | _ _ _ 4 1 | | 11 | _ _ _ 4 2 | | 12 | _ _ _ 4 4 | | 13 | _ _ 1 1 1 | | 14 | _ _ 1 1 2 |

. . .

3진수처럼 1, 2, 4가 반복되니 1을 빼고 mod 3을 해주면 될듯 하다.

좀더 써보면, 오른쪽에서 두 번째 자릿수는 첫 3개를 제외하고 3개씩 반복된다.

| n | 124나라 | | 1 | _ _ _ _ 1 | | 2 | _ _ _ _ 2 | | 3 | _ _ _ _ 4 | | 4 | _ _ _ 1 1 | | 5 | _ _ _ 1 2 | | 6 | _ _ _ 1 4 | | 7 | _ _ _ 2 1 | | 8 | _ _ _ 2 2 | | 9 | _ _ _ 2 4 | | 10 | _ _ _ 4 1 | | 11 | _ _ _ 4 2 | | 12 | _ _ _ 4 4 | | 13 | _ _ 1 1 1 | | 14 | _ _ 1 1 2 | | 15 | _ _ 1 1 4 | | 16 | _ _ 1 2 1 | | 17 | _ _ 1 2 2 | | 18 | _ _ 1 2 4 | | 19 | _ _ 1 4 1 | | 20 | _ _ 1 4 2 | | 21 | _ _ 1 4 4 | | 22 | _ _ 2 1 1 | | 23 | _ _ 2 1 2 |

. . .

$n$ /= $3$ 을 해주면, 3개씩 묶어준것과 같고,

| n | 124나라 | | 1 | _ _ _ _ 1 | | 4 | _ _ _ 1 1 | | 7 | _ _ _ 2 1 | | 10 | _ _ _ 4 1 | | 13 | _ _ 1 1 1 | | 16 | _ _ 1 2 1 | | 19 | _ _ 1 4 1 | | 22 | _ _ 2 1 1 |

. . .

두번째 자리수도, 1을 빼고 mod 3을 해주면 구할 수 있다. 이걸 반복.

#Code

import java.util.*;

class Solution {
    public String solution(int n) {
        StringBuilder ans= new StringBuilder();
        while (n > 0) {
            int rem= (n-1)%3;
            if (rem == 0) ans.insert(0, "1");
            if (rem == 1) ans.insert(0, "2");
            if (rem == 2) ans.insert(0, "4");
            n= (n-1)/3;
        }
        return ans.toString();
    }
}

#Complexity

• Time: $O(log_{3} n)$
• Space: $O(1)$