[Algorithm] 프로그래머스 레벨2 124나라의 숫자

코딩테스트 연습 - 124 나라의 숫자

 

10진법	124나라	10진법	124나라
1	1	6	14
2	2	7	21
3	4	8	22
4	11	9	24
5	12	10	41

500,000,000 이하의 자연수 n이 매개변수로 주어질 때,

n을 124 나라에서 사용하는 숫자로 바꾼 값을 return해주는 함수를 작성하는 문제입니다.

효율성 테스트 실패 코드

    public String failSolution(int n) {

        String answer = "";
        int rest = 0;

        while(n > 0) {
            rest = n % 3;
            n /= 3;
            if(rest == 0) {
                rest = 4;
                n -= 1;
            }
            answer = rest + answer;
        }

        return answer;
    }

 

효율성 테스트에 통과하지 못해서, 다른 사람의 풀이 중 좋아요가 가장 많은 코드를 분석해보도록 하겠습니다.

    public String solution(int n) {
        String[] num = {"4", "1", "2"};
        String answer = "";

        while(n > 0) {
            answer = num[n % 3] + answer; // #1
            n = (n - 1) / 3; // #2
        }
        return answer;
    }

#1

124 나라에서 사용하는 숫자가 3개인 점을 이용해 3진법을 이용합니다.

진법 계산을 위해 3으로 n을 mod 연산한 값과 answer을 더해준 값을 answer에 저장해줍니다.

나머지가 0인 값은 4로 치환해주기 위해 num 배열의 0번째 인덱스에는 4가 들어있습니다.

#2

이 풀이의 핵심은 #2에서 다음 자릿수를 계산할 때 이어서 n을 3으로 나누어 주는 것이 아닌,

n - 1을 계산해준 값을 3으로 나누어 주는 것입니다. 

 

다음 표를 참고하도록 하겠습니다.

 

정수 1,2번째 자리를 보겠습니다.

삼진수는 1과 10

십진수는 1과 3입니다.

 

이 점을 이용하여,

3으로 나누면, 자릿수가 당겨진다는 점을 알 수 있습니다.

 

 

 

 

 

 

다음 표를 참고해서 자릿수가 변하는 것을 확인해보겠습니다.

 

삼진법의 10과, 100을 보면 십진수로 3, 9 입니다.

제곱수 별로 자릿수가 증가하는 것을 볼 수 있습니다.

 

9를 3으로 나누어 준면 3이므로 자릿수가 줄어들게 됩니다.

 

이제 좌측 표의 십진법을 0부터 본다면 0, 1, 2, 3 삼진법은 0, 1, 2, 10

네 번째 자리에서 자릿수가 늘어납니다.

 

문제에서의 표를 보면 1부터 세기 때문에 십진법의 3에서 자릿수가 증가하는 것이 아니라

4에서 자릿수가 증가하고 다음에도 좌측표와 달리 자릿수의 값이 7에서 증가합니다.

 

삼진법의 자릿수를 맞춰주기 위해 -1을 해줍니다.

 

 

 

 

 

 

 

 

 

 

틀린 부분은 말씀해주시면 수정하도록 하겠습니다.

삼진법 - 위키백과, 우리 모두의 백과사전