[12899] 124 나라의 숫자

✔ 124 나라의 숫자

[프로그래머스 12899]

문제 분석하기

최악의 경우의 n이 5억이므로 하나씩 숫자를 올려가는 다이내믹 프로그래밍은 시간 초과가 발생함

그러므로 규칙을 찾아서 해결

 

1, 2, 4, 

11, 12, 14,

21, 22, 24,

41, 42, 44,

111, 112, 114,

121, 122, 124,

141, 142, 144

211, 212, 214,

221, 222, 224,

241, 242, 244,

411, 412, 414,

421, 422, 424,

441, 442, 444

규칙을 가지고 수를 표현

 

예1) 5일 때

5 % 3 = 2

(5 - 1) / 3 = 1

1 % 3 = 1

(1 - 1) / 3 = 0

5는 12

 

예2) 6일 때

6 % 3 = 0 → 4

(6 - 1) / 3 = 1

1 % 3 = 1

(1 - 1) / 3 = 0

6은 14

손으로 풀어보기

1. n을 3으로 나눈 값의 나머지에 따라 answer의 앞에 1, 2, 4를 저장
   • 나머지가 0일 경우, 4를 저장
   • 나머지가 1일 경우, 1을 저장
   • 나머지가 2일 경우, 2를 저장
2. (n - 1) / 3으로 n을 갱신
3. n이 0보다 클 때 동안 이를 반복한 후 answer을 반환

슈도코드 작성하기

n(자연수)
answer(n을 124 나라에서 사용하는 숫자로 바꾼 값 StringBuilder)
numbers(4, 1, 2를 저장한 배열)
while(n이 0보다 클 동안) {
    remain(나머지 값) = n % 3
    answer.insert(0, numbers[remain[)
    n = (n - 1) / 3
}
answer를 문자열로 변환하여 반환

코드 구현하기

/**
 * 12899) 124_나라의_숫자
 */
public class L004_12899 {
    // n(자연수)
    public String solution(int n) {
        // answer(n을 124 나라에서 사용하는 숫자로 바꾼 값 StringBuilder)
        StringBuilder answer = new StringBuilder();
        // numbers(4, 1, 2를 저장한 배열)
        String[] numbers = { "4", "1", "2" };
        // n이 0보다 클 동안
        while (n > 0) {
            // remain(나머지 값) 계산
            int remain = n % 3;
            // n을 3으로 나눈 값의 나머지를 answer의 앞에 저장
            answer.insert(0, numbers[remain]);
            // (n - 1) / 3으로 n을 갱신
            n = (n - 1) / 3;
        }
        // answer를 문자열로 변환하여 반환
        return answer.toString();
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L004_12899 solution = new L004_12899();

        int n = 1;

        String result = solution.solution(n);

        System.out.println(result);
    }
}