강준현

강준현

개발자

[programmers] 124 나라의 숫자

3 분 소요


2. 문제 설명

124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다.

  1. 124 나라에는 자연수만 존재합니다.
  2. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다.

예를 들어서 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

자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요.

3. 제한 사항

  • n은 500,000,000이하의 자연수 입니다.

4. 입출력 예

n result
1 1
2 2
3 4
4 11

5. 코드 해설

5.1. 반복되는 규칙

반복되는 규칙이 있는 것 같습니다. 이를 정리해보고 원하는 답을 얻을 수 있도록 코드를 작성해보도록 하겠습니다.

10진법 10진법 지수 범위 124 나라수(자릿수) 10진법 10진법 지수 범위 124 나라수(자릿수) 10진법 10진법 지수 범위 124 나라수(자릿수)
1 3^1 이하 1(1) 6 (3^2 + 3^1) 이하 14(2) 11 (3^2 + 3^1) 이하 42(2)
2 3^1 이하 2(1) 7 (3^2 + 3^1) 이하 21(2) 12 (3^2 + 3^1) 이하 44(2)
3 3^1 이하 4(1) 8 (3^2 + 3^1) 이하 22(2) 13 (3^3 + 3^2 + 3^1) 이하 111(3)
4 (3^2 + 3^1) 이하 11(2) 9 (3^2 + 3^1) 이하 24(2) 14 (3^3 + 3^2 + 3^1) 이하 112(3)
5 (3^2 + 3^1) 이하 12(2) 10 (3^2 + 3^1) 이하 41(2) 15 (3^3 + 3^2 + 3^1) 이하 114(3)

15을 예를 들어 설명해보도록 하겠습니다.

  • 15은 27(3^3 + 3^2 + 3^1) 값 이하 12(3^2 + 3^1) 이상입니다.
  • 최대 exp 값은 3 입니다. 탐색을 시작하는 base는 12(3^2 + 3^1) 입니다.
  • 124 나라에서 3자리인 숫자는 총 27 개가 존재합니다.(27 = 3^exp = 3^3)
  • 각 자리 숫자를 지정해보겠습니다. 1, 2, 4 중 하나입니다.
  • 첫 번째 숫자를 지정해보겠습니다. 첫 번째 숫자가 증가함에 따라 10진수는 9(3^2)개씩 커집니다.
    • 3 값은 9(temp) * 1(subIndex) 보다 작거나 같습니다.(3 = n - base = 15 - 12)
    • 맨 앞자리 수는 1(subIndex)가 됩니다.
    • base를 12 + 0(9 * 0) 만큼 증가시켜 12을 만듭니다.
  • 두 번째 숫자를 지정해보겠습니다. 두 번째 숫자가 증가함에 따라 10진수는 3(3^1)개씩 커집니다.
    • 3 값은 3(temp) * 1(subIndex) 보다는 작거나 같습니다.(3 = n - base = 15 - 12)
    • 다음 자리 수는 1(subIndex)가 됩니다.
    • base를 12 + 0(3 * 0) 만큼 증가시켜 12을 만듭니다.
  • 세 번째 숫자를 지정해보겠습니다.
    • 3 값은 1(temp) * 3(subIndex) 보다는 작거나 같습니다.(3 = n - base = 15 - 12)
    • 다음 자리 수는 3(subIndex)이므로 4가 됩니다.
    • base를 12 + 3(1 * 3) 만큼 증가시켜 15을 만듭니다.

6. 제출 코드

class Solution {
    public String solution(int n) {
        int exp = 1;
        int base = 0;
        while (n > base + Math.pow(3, exp)) {
            base += Math.pow(3, exp);
            exp++;
        }
        StringBuffer answer = new StringBuffer();
        for (int index = exp - 1; index >= 0; index--) {
            double temp = Math.pow(3, index);
            int subIndex = 0;
            for (subIndex = 1; subIndex <= 3; subIndex++) {
                if (n - base <= temp * subIndex) {
                    break;
                }
            }
            base += temp * (subIndex - 1);
            if (subIndex == 3) {
                answer.append(4);
            } else {
                answer.append(subIndex);
            }
        }
        return answer.toString();
    }
}

7. BEST PRACTICE

  • 뒤에 자리 수부터 채워나갑니다.
  • n이 0이 될 때까지 반복 수행합니다.
  • 3으로 나눠 떨어지는 경우 4, 나눠 떨어지지 않는 경우 나머지를 이어 붙입니다.
  • 숫자 n을 (n - 1) / 3 만큼 낮춥니다.
class Solution {
    public String solution(int n) {
        String[] num = { "4", "1", "2" };
        String answer = "";
        while (n > 0) {
            answer = num[n % 3] + answer;
            n = (n - 1) / 3;
        }
        return answer;
    }
}

CLOSING

제가 문제를 푼 날은 컨디션이 좋았나봅니다. 오늘의 저는 이해가 안됩니다. 풀어본 문제를 다시 정리해보는 것도 많은 도움이 될 것이라 생각하고 즐거운 마음으로 정리하겠습니다. 규칙을 빠르게 찾아내는 연습과 코드로 옮기는 연습을 열심히 해야겠습니다.

BEST PRACTICE를 보니 정말 감탄밖에 나오지 않습니다. 어떻게 저런 답변이 나올 수 있는지 추리가 되지 않아서 풀이를 찾아보았습니다. 특히 'n = (n - 1) / 3;' 이 분이 어떤 논리를 통해 도출되었는지 정말 놀라울 따름입니다.

3의 배수일 때 다음 자릿수가 1 증가하는게 아니기 때문에 1을 빼주어야 한다.

REFERENCE

참고