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

문제

124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다.
124 나라에는 자연수만 존재합니다.
124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다.
Image for post
자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요.

접근

문제를 보자마자 3진법으로 접근해야 하는 것을 알았다. 그리고 자릿수가 늘어 날때 새로운 규칙이 있는 것을 알았다. 탐색이나 BFS, DFS와 같은 자료구조 형태의 접근이 아닌 규칙을 발견하고 구현하면 되는 문제였다.
방식은 먼저 숫자를 3으로 나누어서 몫과 나머지를 알아낸다. 몫은 나누어서 Math.floor 처리를 했으며 나머지는 모듈로 연산으로 계산했다. 그렇게하면 나머지는 0,1,2가 되고 0인 경우는 4, 1은 1, 2는 2를 추가해준다.
그리고 몫이 3 이상이면 계속해서 위 방식을 반복하는데 단 여기서 나머지가 0인 경우엔 그 다음수가 바로 자릿수가 바뀌는 수가 되므로 새로운 규칙이 생긴다. 바로 다음 계산에 사용할 몫에서 1을 빼주어야 한다는 점이다.
통과한 정답 코드는 아래와 같다. 효율성 계산 통과를 위해 스트링 빌더를 사용해보았다.

import java.util.*;
class Solution {
     public String solution(int n) {
        List<Integer> arr = new ArrayList<>();
        int q = n;
        int r = Integer.MAX_VALUE;
while(q >= 3){
            q = (int)Math.floor(q / 3);
            r = n % 3;
            System.out.println(q);
            System.out.println(r);
            if(r == 0){
                q-=1;
                arr.add(0, 4);
            }else{
                arr.add(0, r);
            }
            n = q;
        }
        if(q != 0){
            arr.add(0, q);
        }
        
        String[] answer = new String[arr.size()];
        for(int i=0; i<arr.size(); i++){
            answer[i] = arr.get(i).toString();
        }
         
        StringBuilder sb = new StringBuilder();
        for (String str : answer){
            sb.append(str);
        }
     return sb.substring(0, sb.length());
    }
}