[프로그래머스] 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)\)