[프로그래머스][JAVA] 3진법 뒤집기

문제설명

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

 

제한사항

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

 

풀이

3진수에 대한 이해

10진수는 한 자리당 0부터 9까지 총 10개의 자연수가 들어갈 수 있다.

이와 마찬가지로 3진수는 한 자리당 0부터 3까지의 자연수가 들어갈 수 있다.

ex. 0(0) -> 1(1) -> 2(2) -> 10(3) -> 11(4) -> 12(5) -> 20(6)

 

알고리즘

1. 10진수를 3진수로 변환했을 때의 자릿수를 구한다. (ex. 45는 3진수로 변환하면 1200이므로 4자릿수이다.)

• 주어진 10진수가 3의 k제곱보다 크다면  k++, 이 과정을 반복하여 자릿수 k를 구한다.

2. 10진수를 3진수 문자열로 변환한다.

• 3진수의 각 자릿수는 3의 제곱수임을 이용하여 주어진 10진수를 3의 제곱수로 나눈 몫을 3진수 문자열에 이어붙여준다.
• 주어진 10진수를 3의 제곱수로 나눈 나머지를 다시 주어진 10진수를 담았던 변수에 대입한다.
• 위 과정을 마지막 자릿수에 도달할 때까지 반복한다. (3진수의 가장 왼쪽 자릿수부터 채워나가게 된다.)

3. 3진수 문자열을 뒤집는다.

4. 뒤집은 문자열의 숫자들을 순회하며 3진수 정수로 변환한다.

• 뒤집은 문자열의 숫자를 순회하며 3의 제곱수를 곱해주면 된다.

코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        int k = 0;
        String strAnswer = "";
        
        // 1. 3진수의 자릿수를 구한다.
        while (Math.pow(3, k) <= n){
            k++;
        }
        // 10진수를 3진수 문자열로 변환한다.
        for (int i = k-1; i >= 0; i--){
            strAnswer += Integer.toString(n / (int)Math.pow(3, i)); // 3의 제곱수로 나눈 몫 이어붙임
            n = n % (int)Math.pow(3, i);    // 3의 제곱수로 나눈 나머지 대입
        }
        // 3진수 문자열을 뒤집고 뒤집은 문자열의 숫자들을 순회하며 3진수 정수로 변환한다.
        for (int i = k-1; i >= 0; i--){
            answer += Math.pow(3, i) * Character.getNumericValue(strAnswer.charAt(i));
        }
        
        return answer;
    }
}

 

성능

 

ERROR

// 잘못된 풀이
while (Math.pow(3, k) < n){
	k++;
}

// 올바른 풀이
while (Math.pow(3, k) <= n){
	k++;
}

처음에는 자릿수를 구하는 while문의 조건에 등호를 넣지 않았다.

그러나 주어진 10진수(n)가 3이라면 3진수 자릿수(k)가 2자리(3진수로 변환 시 10이 되기 때문)이어야 하는데,

등호를 넣지 않으면 k=1인 상태에서 while문을 탈출하게 되므로 잘못된 답을 도출하게 된다.

 

좀 더 신중하게 조건을 확립해야함을 깨달았다.

 

다른 풀이

// 10진수 -> 3진수 변환 알고리즘
while(n > 0){
	int r = n % 3;
    n = n / 3;
    str = r + str;
}

// Integer.toString()과 Integer.parseInt()를 이용한 변환
Integer.toString(정수, n진법);	// 주어진 정수를 n진법을 적용한 문자열로 변환
Integer.parseInt(문자열, n진법);	// 주어진 n진법 문자열을 정수로 변환