3진법 뒤집기

---

🔗 🔗 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;
	}
}