𝝅번째 알파카의 개발 낙서장

screen

[프로그래머스 / JAVA] Level 1 3진법 뒤집기 (68935)

posts

알고리즘

시리즈 톺아보기

프로그래머스

프로그래머스
count

3진법 뒤집기 🔗

랭크 사용 언어
Level 1 JAVA

🔗 3진법 뒤집기

문제 설명 🔗

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

제한사항 🔗

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

입출력 예 🔗

n result
45 7
125 229

입출력 예 설명 🔗

입출력 예 #1

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

n (10진법) n (3진법) 앞뒤 반전(3진법) 10진법으로 표현
45 1200 0021 7

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

입출력 예 #2

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

n (10진법) n (3진법) 앞뒤 반전(3진법) 10진법으로 표현
125 11122 22111 229

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

풀이 🔗

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

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

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

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


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

JAVA

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

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

JAVA

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

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

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

코드 🔗

JAVA

0import java.util.ArrayList;
1import java.util.Collections;
2
3/**
4 * 3진법 뒤집기 클래스
5 *
6 * @author RWB
7 * @since 2021.12.12 Sun 00:47:33
8 */
9class Solution
10{
11 /**
12 * 해답 반환 메서드
13 *
14 * @param n: [int] 자연수
15 *
16 * @return [int] 해답
17 */
18 public int solution(int n)
19 {
20 ArrayList<Integer> list = dec2ter(n);
21
22 Collections.reverse(list);
23
24 return ter2dec(list);
25 }
26
27 /**
28 * 10진법 -> 3진법 배열 반환 메서드
29 *
30 * @param num: [int] 자연수
31 *
32 * @return [ArrayList] 3진법 배열
33 */
34 private ArrayList<Integer> dec2ter(int num)
35 {
36 ArrayList<Integer> list = new ArrayList<>();
37
38 int max = 0;
39
40 while (Math.pow(3, max) <= num)
41 {
42 max++;
43 }
44
45 for (int i = max - 1; i > -1; i--)
46 {
47 int pow = (int) Math.pow(3, i);
48
49 list.add(num / pow);
50
51 num %= pow;
52 }
53
54 return list;
55 }
56
57 /**
58 * 3진법 -> 10진법 반환 메서드
59 *
60 * @param nums: [ArrayList] 3진법 배열
61 *
62 * @return [int] 10진법 숫자
63 */
64 private int ter2dec(ArrayList<Integer> nums)
65 {
66 int flag = nums.size() - 1;
67
68 int answer = 0;
69
70 for (int num : nums)
71 {
72 answer += (int) Math.pow(3, flag) * num;
73
74 flag--;
75 }
76
77 return answer;
78 }
79}