🔗 3진법 뒤집기

자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요.

• n은 1 이상 100,000,000 이하인 자연수입니다.

입출력 예 #1

답을 도출하는 과정은 다음과 같습니다.

따라서 7을 return 해야 합니다.

입출력 예 #2

답을 도출하는 과정은 다음과 같습니다.

따라서 229를 return 해야 합니다.

임의의 숫자를 3진법으로 치환하여 역순으로 배열하고, 이를 다시 10진법으로 치환하는 알고리즘이다.

1. 10진법 -> 3진법 변환 알고리즘
2. 3진법 -> 10진법 변환 알고리즘

10진법과 3진법의 자유로운 변환이 이루어지도록 변환 모듈을 구성하는 것이 좋아보인다.

또한, 3진법에서 숫자를 역순으로 배치해야하니, 각 숫자를 따로따로 List에 할당하여 한번에 역순으로 돌려버리는 방법을 차용하고자 한다.

10진법에서 3진법으로 변환하는 메소드는 아래와 같다.

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private ArrayList<Integer> dec2ter(int num)
{
    ArrayList<Integer> list = new ArrayList<>();
    
    int max = 0;
    
    while (Math.pow(3, max) <= num)
    {
        max++;
    }
    
    for (int i = max - 1; i > -1; i--)
    {
        int pow = (int) Math.pow(3, i);
        
        list.add(num / pow);
        
        num %= pow;
    }
    
    return list;
}

정수 형태의 3진법은 크게 의미가 없다. 0이 앞에 나오게 되면 정수형으로 변환되면서 유실될 가능성도 크고, 굳이 정수형에서의 연산이 필요 없기 때문. 따라서 ArrayList<Integer>로 반환한다.

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private int ter2dec(ArrayList<Integer> nums)
{
    int flag = nums.size() - 1;
    
    int answer = 0;
    
    for (int num : nums)
    {
        answer += (int) Math.pow(3, flag) * num;
        
        flag--;
    }
    
    return answer;
}

3진법 -> 10진법 변환 알고리즘은 위와 같다.

dec2ter으로 3진법 배열을 받아서, 이를 역순으로 배열하고 다시 ter2dec 메서드로 변환하면 된다. Collections.reverse() 메서드를 통해 List 같은 Collection 객체의 역순 배열을 수행할 수 있다.

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import java.util.ArrayList;
import java.util.Collections;

/**
 * 3진법 뒤집기 클래스
 *
 * @author RWB
 * @since 2021.12.12 Sun 00:47:33
 */
class Solution
{
    /**
     * 해답 반환 메서드
     *
     * @param n: [int] 자연수
     *
     * @return [int] 해답
     */
    public int solution(int n)
    {
        ArrayList<Integer> list = dec2ter(n);
        
        Collections.reverse(list);
        
        return ter2dec(list);
    }
    
    /**
     * 10진법 -> 3진법 배열 반환 메서드
     *
     * @param num: [int] 자연수
     *
     * @return [ArrayList] 3진법 배열
     */
    private ArrayList<Integer> dec2ter(int num)
    {
        ArrayList<Integer> list = new ArrayList<>();
        
        int max = 0;
        
        while (Math.pow(3, max) <= num)
        {
            max++;
        }
        
        for (int i = max - 1; i > -1; i--)
        {
            int pow = (int) Math.pow(3, i);
            
            list.add(num / pow);
            
            num %= pow;
        }
        
        return list;
    }
    
    /**
     * 3진법 -> 10진법 반환 메서드
     *
     * @param nums: [ArrayList] 3진법 배열
     *
     * @return [int] 10진법 숫자
     */
    private int ter2dec(ArrayList<Integer> nums)
    {
        int flag = nums.size() - 1;
        
        int answer = 0;
        
        for (int num : nums)
        {
            answer += (int) Math.pow(3, flag) * num;
            
            flag--;
        }
        
        return answer;
    }
}