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

 

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

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

 

프로그래머스 Lv2 문제이며, 카테고리를 묶자면 시뮬레이션 문제로 보인다.

문제를 요약하자면, n 값을 입력받아서 124 나라의 숫자 문법에 맞게 문자열을 출력하는 문제이다.

 

예를 들어, 1 -> 1,  2 -> 2, 3 -> 4, 4 -> 11, 5 -> 12, 6 -> 14, 7 -> 21 ... 13 -> 111 ... 39 -> 444 순으로 이어지는 문법에서 특정 n 값을 넣었을 때 값을 출력해야 한다.

 

문제를 해결하기 위해서 자리수를 구분하기 위한 배열을 생성한다.

 

인덱스	숫자
0	3
1	12 (+9)
2	39 (+27)
3	120 (+81)
4	363 (+243)

 

위에 표를 보면, 3^(인덱스+1) 만큼 값이 더해지는 것을 확인할 수 있다.

 

예를 들어 10 을 입력 받으면 어떻게 처리해야 할까??

 

10 은 우선 3 과 12 사이에 있기 때문에 구간 별 차이 값과 10과 3의 차이를 구한다음 범위에 따라 1, 2, 4 중 선택해서 문자열에 추가하는 방식으로 구현하고, 잔여 숫자를 이에 맞춰 빼는 방식으로 구현하면 된다.

 

구간 값 차이 : 9

10 - 3 차이 : 7

 

여기서, 7 은 6 보다 크고 9 보다 작거나 같기 때문에 해당 인덱스에 맞는 숫자는 4 이다.

여기서 해야 될것은 10 에서 구간 값 차이인 9를 뺀다. 그럼 1이 남고 1은 그대로 추가하면 된다.

(여기서 유의할 것으로 3이 마지막에 남은 경우, 4를 추가해야 한다)

 

테스트를 통과한 코드는 아래와 같다.

 

import java.util.*;
class Solution {
    public static String solution(int n) {
        String answer = "";
        // n이 3이하이면 미리 예외처리한다.
        if (n <= 3) {
            if (n % 3 == 1) return "1";
            if (n % 3 == 2) return "2";
            if (n % 3 == 0) return "4";
        }

        List<Integer> list = new ArrayList<>();
        list.add(3);
        int base = 3;
        // n 보다 작거나 같을 때 까지 기준표를 만든다.
        while (list.get(list.size()-1) < n) {
            int last = list.get(list.size()-1);
            list.add(last + base * 3);
            base *= 3;
        }
        // remain 의 초기값으로 n 을 설정하고, 아래 루프를 돌면서 문자열을 만든다.
        int remain = n;
        for (int i = list.size()-1; i > 0; i--) {
            int diff = list.get(i) - list.get(i-1);
            int curDiff = remain - list.get(i-1);

            if (curDiff > 0 && curDiff <= diff / 3) {
                answer += "1";
                remain -= diff / 3;
            } else if (curDiff > diff / 3 && curDiff <= diff * 2 / 3) {
                answer += "2";
                remain -= diff * 2 / 3;
            } else {
                answer += "4";
                remain -= diff;
            }
        }
        // 마지막에 남은 숫자를 문자열 끝에 추가해야 한다
        if (remain % 3 == 1) answer += "1";
        if (remain % 3 == 2) answer += "2";
        if (remain % 3 == 0) answer += "4";
        return answer;
    }
}