Problem


Key Idea

분명 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을 해주면 구할 수 있다. 이걸 반복.

  • Time: \(O(log_{3} n)\)


Implementation

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();
    }
}

Tags:

Updated:

Leave a comment