3진법 뒤집기

Posted on Edited on In , ,

문제정의

어떤 십진수 n이 들어올 때 이를 3진법으로 바꾼뒤 이를 뒤집는다. 뒤집은 3진법을 다시 10진수로 출력한다.

문제풀이

10진법을 2진법을 바꾸는 방법을 떠올려보자. 계속 나누어가다가 몫이 0이 되면 나머지들을 최근것부터 합치면 된다. 이 문제에서는 3진법을 거꾸로 뒤집으라 했으므로 나오는 나머지들을 스택에 쌓으면 원래 3진법에서 뒤집어진다. 뒤집은 수를 10진법으로 바꾸는 방법은 3^(자릿수)에 해당 값을 곱하면된다. 이를 다 합산하면 우리가 바라던 정답이다.

전체 코드는 다음과 같다. 

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
import java.util.*;

public class Flip3Digit {
    
    public static void main(String[] args)
    {
        int n = 45;
        int answer = 0;
        int q = 1, r = 0;
        Stack<Integer> s = new Stack<>();
        while(q != 0)
        {
            q = n/3;
            r = n%3;
            n /= 3;
            s.push(r);
            
        }
        int digit = 0;
        while(!s.empty())
        {
            answer += Math.pow(3,digit) * Integer.parseInt(s.peek().toString());
            digit++;
            s.pop();
        }
        System.out.print(answer);
    }
    
}
부분부분 살펴보자 
1
2
3
4
5
6
7
8
9
10
11
12
int n = 45;
int answer = 0;
int q = 1, r = 0;
Stack<Integer> s = new Stack<>();
while(q != 0)
{
    q = n/3;
    r = n%3;
    n /= 3;
    s.push(r);
        
}
10진법을 3진수로 바꾸는 과정이다. q는 몫이고 r은 나머지이다. 몫이 0이 될 때 까지 나머지를 구하고 이를 스택에 쌓는다. 
1
2
3
4
5
6
while(!s.empty())
{
    answer += Math.pow(3,digit) * Integer.parseInt(s.peek().toString());
    digit++;
    s.pop();
}
스택에 나머지값이 쌓이면 스택에 쌓인 값 순서대로 10진수로 변환하는 과정을 거친다. 이 때 자릿수를 나타내는 digit은 0으로 초기화한다. 그리고 3*(자릿수)를 각 나머지에 곱하고 digit을 늘려간다.

총 시간복잡도는 3진수로 바꿨을 때 최대 자릿수를 n이라하면 \(O(n)\)이다.

테스트