[알고리즘] Programmers - 124 나라의 숫자

프로그래머스

문제 설명

• 124 나라에는 자연수만 존재한다.
• 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용한다.
• 자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 반환해야 한다.
• n의 범위는 1 <= n <= 50,000,000 이다.

문제 해결

• StringBuilder를 이용해 문자열 처리 시간을 단축했다.
• 3진수를 잘 이용해서 변환하면 구현 가능하다.
• 일반 3진수는 0이 있어서 일반적인 숫자 체계처럼 가장 앞의 숫자가 0으로 올 수 없지만, 124 나라에서의 진수는 11처럼 가장 앞의 숫자로 가장 작은 단위의 숫자가 올 수 있다.
• 3의 배수는 3으로 나눴을 때 나머지가 0인데, 124 나라의 숫자에서는 마지막에 4를 가지고 있다.
• 3의 배수에 대해서 4로 처리하고, 몫에 대해서 1을 빼면 해결할 수 있다.

시간 복잡도

• O(log₃(n))

풀이 코드

import java.util.*;

class Solution {
    public String solution(int n) {
        StringBuilder sb = new StringBuilder();
        
        while(n > 0) {
            int next = n % 3;
            if (next == 0) {
                next = 4;
                n--;
            }
            
            sb.insert(0, next);
            n /= 3;
        }
        
        return sb.toString();
    }
}

결과