[200520] 124 나라의 숫자 - 연습문제(level2)

1. 문제이해

- 10진법의 수를 124 나라의 숫자로 변경하기

: 1, 2, 4를 써서 표현할 수 있는 숫자들의 오름차순 배열로 표현

 

2. 전략

(1) 자릿수 결정

- Math.pow(3, size)를 size가 1일 때부터 더해서 범위의 시작값 구하기

(ex> 3+9+27(Math.pow(3, 3)까지) < n <= 3+9+27+81(Math.pow(3, 4)까지)라면 "4자릿수")

 

(2) 자릿수 내에서 앞에서 부터 숫자 결정

- gap = (int) Math.pow(3, 자릿수-1)
1. n <= num+gap
: "1" 추가, 범위 시작값 = num
2. n <= num+gap*2
: "2" 추가, 범위 시작값 = num+gap
3. n <= num+gap*3
"4" 추가, 범위 시작값 = num+gap*2

 

3. 참고사항

- 다른 풀이 : 사실상 "3진수"와 비슷

- n%3이 1이면 1, 2이면 2, 0이면 4로 처리 --> 앞에 붙이기(뒤부터 채워나감)
- n = (n-1)/3과 연산 계속 -- 자리올림 방지(나누어 떨어지는 경우 n으로 하면 문제가 생김)

4. 코드

class Solution {
    public String solution(int n) {
        String answer = "";
        int size = 0, num = 0;
        while(num < n){
            size++;
            num += Math.pow(3, size);
        }
        num -= Math.pow(3, size); //범위 시작값
        for(int i = size-1; i >= 0; i--){
            int gap = (int)Math.pow(3, i);
            if(n <= num + gap){
                answer += "1";
            }
            else if(n <= num + gap*2){
                answer += "2";
                num += gap;
            }
            else if(n <= num + gap*3){
                answer += "4";
                num += gap*2;
            }
        }
        return answer;
    }
}