Programmers | Level 2 | 124 나라의 숫자

Sep 07, 2024

Published byJynn

999

Programmers | Level 2 | 124 나라의 숫자

Problems

📘 Src: Programmers
🗂️ Cat: Math

󰧭 Description

124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다.

124 나라에는 자연수만 존재합니다.
124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다.

예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다.

10진법	124 나라	10진법	124 나라
1	1	6	14
2	2	7	21
3	4	8	22
4	11	9	24
5	12	10	41

󰦕 Examples

n	result
1	1
2	2
3	4
4	11

Solutions

󰘦 Code

Solution.java

import java.util.*;

class Solution {
    public String solution(int n) {
        // 124 나라의 숫자 변환을 위한 배열: 0 -> 4, 1 -> 1, 2 -> 2
        int[] digits = new int[]{4, 1, 2};  
        // 결과를 저장할 StringBuilder
        StringBuilder sb = new StringBuilder();
        
        // n이 0이 될 때까지 몫과 나머지를 이용해 변환
        while (n > 0) {
            int quotient = n / 3;           // n을 3으로 나눈 몫을 구함
            int remainder = digits[n % 3];  // 나머지 값을 변환 (0 -> 4, 1 -> 1, 2 -> 2)
            // 나머지가 0인 경우 몫을 하나 줄여서 다음 자릿수로 넘김
            if (remainder == 4) quotient--;
            
            sb.append(remainder); // 변환된 숫자를 결과에 추가
            n = quotient; // 몫을 n으로 갱신하여 다음 반복 준비
        }
        
        // 결과를 뒤집어 올바른 순서로 반환
        return sb.reverse().toString();
    }
}

 Approach

이 문제는 주어진 자연수 n을 124 나라의 숫자 체계로 변환하는 수학 문제입니다. 124 나라의 숫자는 1, 2, 4만을 사용하며, 이를 처리하기 위해 3진법을 변형한 방식을 사용합니다.

1. 문제 분석

124 나라는 10진법이 아닌 독특한 숫자 체계를 사용하여 숫자를 표현합니다. 이 나라에서는 1, 2, 4만 사용하며, 3을 기반으로 숫자를 변환합니다. 즉, 우리가 아는 10진법을 그대로 사용할 수 없고, 이를 3진법과 유사한 방식으로 처리해야 합니다.

주요 특징은, 숫자를 3으로 나누었을 때 나머지에 따라 1, 2, 4로 변환된다는 점입니다. 나머지가 1이면 1, 나머지가 2면 2, 나머지가 0일 때는 4로 변환됩니다. 다만, 나머지가 0일 때는 몫에서 1을 빼주어야 한다는 특수한 규칙이 있습니다. 이 과정을 반복하여 주어진 숫자를 124 나라의 숫자 체계로 변환할 수 있습니다.

2. 접근 방식

이 문제를 해결하기 위해서는 주어진 자연수 n을 3으로 나눈 나머지를 이용하여 124 나라의 숫자로 변환하는 방식이 필요합니다. 이 과정에서 반복적으로 몫과 나머지를 계산하며, 이를 124 나라의 숫자 체계로 변환합니다.

124 나라의 숫자 체계는 일반적인 3진법과 달리 0이 존재하지 않습니다. 나머지가 0이 나오는 경우에는 0을 4로 치환하고, 자릿수를 정확하게 맞추기 위해 몫에서 1을 빼는 특수한 처리가 필요합니다. 이는 124 나라의 숫자 체계가 1부터 시작하는 1베이스 체계이기 때문입니다. 일반적인 3진법에서는 나머지가 0일 경우 몫을 그대로 사용하지만, 124 나라에서는 나머지가 0일 때 몫에서 1을 빼주어야 올바르게 계산됩니다.

주요 변환 과정은 다음과 같이 이루어집니다:

나머지 치환: n을 3으로 나눈 나머지를 구한 후, 나머지가 1이면 1, 2면 2, 0이면 4로 변환합니다.
몫 갱신: 나머지를 처리한 후, 몫에서 1을 뺀 값을 다음 반복에서의 n으로 갱신하며, 몫이 0이 될 때까지 이 과정을 반복합니다.
숫자 조합: 변환된 숫자들을 차례로 이어붙여 문자열을 구성하고, 최종적으로 역순으로 변환하여 결과를 반환합니다.

3. 초기화 및 반복 구조

124 나라의 숫자 체계는 3으로 나눈 나머지를 기준으로 변환됩니다. 나머지 값에 따라 1, 2, 4로 빠르게 변환하기 위해, 조건문을 사용하지 않고 미리 배열에 초기화를 해두고 매핑하여 처리합니다. 이를 통해 값을 빠르게 참조할 수 있으며, 반복적인 연산에서 효율성을 높일 수 있습니다.

Solution.java

int[] digits = new int[]{4, 1, 2};  // 124 나라의 숫자를 저장할 배열
StringBuilder sb = new StringBuilder();  // 결과를 저장할 StringBuilder

4. 몫과 나머지를 이용한 변환

자연수 n을 3으로 나누고 나머지를 이용해 124 나라의 숫자로 변환합니다. 이때 3으로 나눈 몫이 0이 될 때까지 반복하며, 나머지에 따라 1, 2, 4를 추가합니다. 나머지가 0일 때는 특별히 이를 4로 처리하고, 몫을 1 줄여서 다음 계산에 반영하는 방식으로 접근합니다.

Solution.java

while (n > 0) {
    int quotient = (n - 1) / 3;  // 3으로 나눈 몫을 구함 (124나라의 규칙 적용)
    int remainder = n % 3;  // 나머지를 구함
    sb.append(digits[remainder]);  // 나머지에 맞는 숫자 추가 (0 -> '4', 1 -> '1', 2 -> '2')
    ...
}

5. 변환된 숫자 저장 및 다음 반복 준비

변환된 숫자를 StringBuilder에 저장한 후, 몫을 n에 할당하여 다음 반복을 준비합니다. 이 과정은 자연수 n을 몫과 나머지를 계속해서 처리해 나가는 방식으로, 모든 자릿수의 변환이 완료될 때까지 반복됩니다.

Solution.java

while (n > 0) {
    ...
    
    sb.append(digits[remainder]);  // 변환된 숫자를 문자열에 저장
    n = quotient;  // 몫을 n에 할당하여 다음 반복 준비
}

6. 결과 반환

변환 과정에서 숫자는 마지막 자릿수부터 차례대로 StringBuilder에 추가되므로, 올바른 순서를 얻기 위해 문자열을 뒤집어야 합니다. 이를 위해 StringBuilder의 reverse() 메서드를 사용하여 문자열을 뒤집고, 최종 변환된 값을 반환합니다.

Solution.java

// 문자열을 뒤집어 올바른 순서로 반환
return sb.reverse().toString();

이 과정을 통해 n을 124 나라의 숫자로 변환하여 정확한 결과를 반환하게 됩니다.

󰄉 Complexity

⏳ TC: O(log(n))
💾 SC: O(log(n))

주어진 숫자 n을 3으로 나누는 과정에서 매번 자릿수가 줄어들기 때문에 시간 복잡도는 O(log(n))입니다. 또한, 변환된 결과를 저장하는 데 사용되는 공간도 자릿수에 비례하므로, 공간 복잡도 역시 O(log(n))입니다.

Algorithm
Math