문제정의
어떤 십진수 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이라하면 이다.
테스트