[프로그래머스] 124 나라의 숫자 - Java

문제: https://programmers.co.kr/learn/courses/30/lessons/12899

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

풀이과정

124나라에서는 1, 2, 4 세 가지 숫자만을 사용하여 모든 자연수를 표현한다. 

먼저 이 숫자의 규칙성을 찾기 위해 10진법 숫자와, 3진법 숫자, 그리고 124 나라의 숫자를 비교 해 보았다.

10진법 수	3진법 수	124 나라의 숫자
1	1	1
2	2	2
3	10	4
4	11	11
5	12	12
6	20	14
7	21	21
8	22	22
9	100	24
10	101	41
11	102	42
12	110	44
13	111	111
14	112	112
15	120	114

여기서 124나라의 숫자에서 4가 나타나는 경우를 살펴보면 다음과 같은 규칙을 찾을 수 있다. (124 나라의 숫자를 뒤에서부터 채워나가는 방식)

1. 3진법 수로 0이 나타나는 위치에 124나라의 숫자 4가 나타난다.
2. 해당 0보다 앞에 있는 숫자들(3진법 수)에서 1(10진법 수)을 뺀 값이 124나라의 숫자의 4의 앞에 나타난다.

즉, 예를들어 10진법 수 12와 15의 경우를 살펴보면 다음과 같은 과정을 거치게 된다.

• 10진법 수 12의 경우
  • 3진법 수로 나타내면 110이다. 맨 뒤에서 0이 나타나므로 124 나라의 숫자로 표현할 때 맨 뒷자리 숫자는 4가 된다.
  • 0보다 앞에 있는 숫자는 3진법 수 11이다. 여기서 1을 빼면 10이다. (= 3진법 수 11 - 10진법 수 1)  
  • 다시 0이 나타나므로 124 나라의 숫자로 표현할 때 뒤에서 두 번째 숫자도 4이다.
  • 0보다 앞에 있는 숫자는 3진법 수 1이다. 여기서 1을 뺴면 0이다.
  • 124나라의 숫자는 자연수만을 다룬다. 따라서 0은 고려하지 않고 최종 결과는 44이다.
• 10진법 수 15의 경우
  • 3진법 수 120 → 124 나라의 숫자 맨 뒷자리 4
  • 남은 숫자는 11이다. (0보다 앞에 있는 3진법 수 12 - 10진법 수 1 = 3진법 수 11)
  • 3진법 수 11은 그대로 124 나라의 숫자로 바꾸어도 11이 된다. 따라서 최종 결과는 114이다.

여기까지 보았을 때, 3진법 수의 가장 마지막 자리 숫자는 주어진 10진법 수를 3으로 나눈 나머지이고, 그보다 앞에 있는 숫자들은 3으로 나눈 몫에 해당하므로 다음과 같이 다시 간단히 바꾸어 정리할 수 있다.

• 10진법 수 12의 경우
  • 12 % 3 = 0
    • 124 나라의 숫자: 4
    • 나머지가 0 이므로 12 / 3 = 4에서 1을 빼 주어 3이 된다.
  • 3 % 3 = 0
    • 124 나라의 숫자: 44
    • 나머지가 0 이므로 3 / 3 = 1 에서 1을 빼 주어 0이 된다.
  • 최종 결과: 124 나라의 숫자 44
• 10진법 수 15의 경우
  • 15 % 3 = 0
    • 124나라의 숫자: 4
    • 나머지가 0 이므로 15 / 3 = 5에서 1을 빼 주어 4가 된다.
  • 4 % 3 = 1
    • 124 나라의 숫자: 14
    • 나머지가 0이 아니므로 4 / 3 = 1
  • 1 % 3 = 1
    • 124나라의 숫자: 114
    • 나머지가 0이 아니므로 1 / 3 = 0
  • 최종 결과: 124 나라의 숫자 114

정리를 끝낸 후에는 굉장히 간단한 코드로 해결 할 수 있는 문제였는데, 정리하기 전에 10진법과 3진법을 오가는 계산으로 인해 괜히 복잡하게 느껴졌던 문제였다. 

소스코드

class Solution {
    public String solution(int n) {
        StringBuilder sb = new StringBuilder();

        while (n > 0) {
            int quotient = n / 3;
            int remainder = n % 3;

            switch (remainder) {
                case 1: case 2:
                    sb.insert(0, remainder);
                    break;
                case 0:
                    sb.insert(0, '4');
                    break;
            }

            n = remainder == 0? quotient - 1 : quotient;
        }

        return sb.toString();
    }
}