[프로그래머스/Java] N진수 게임 (feat. Java 진법 변환)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/17687?language=java

프로그래머스

N진수 게임은, `m`명의 인원이 0부터 차례로 `n`진수의 숫자를 한 자릿수 씩 말하는 게임이다.

2진수를 예로 들면, 한 명씩 차례로 `0, 1, 1, 0, 1, 1, 1, 0, 0, ...` 이런 식으로 숫자를 하나씩 말한다.

`p`번째로 숫자를 말해야 하는 사람이 자신이 앞으로 말해야 할 `t`개의 숫자를 미리 계산하려고 한다.

• 2 ≤ `n` ≤ 16
• 0 ≤ `t` ≤ 1,000
• 2 ≤ `m` ≤ 100
• 1 ≤ `p` ≤ `m`

 

풀이

우선 0부터 `n`진법으로 숫자를 나열해주었다. `n`진법으로 변환해서 문자열로 반환하는 함수인 `decimalToBaseN`을 작성해줬다. 10진수를 `n`진수로 변환하는 알고리즘은 다음과 같다.

1. 10진수 `decimal`의 나머지를 구한다.
2. `decimal`을 `n`으로 나눈다.
3. 1~2의 과정을 `decimal`이 0보다 클 때까지 반복한다.
4. 나머지를 역순으로 나열하면 n진수가 완성된다.

⚠️해당 문제에서 주의할 점은 나머지가 10이 넘어갈 경우, 16진수까지 커버할 수 있는 `A~F`로 처리해줘야 한다는 것이다.

 

빠른 문자열 조합을 위해 `StringBuilder`를 사용했는데, 나머지를 역순으로 나열하기 위해 `insert(0, remainder)`로 작성했다. `StringBuilder`의 `insert(int offset, String str)` 메서드를 사용하면 `offset` 인덱스에 문자열 `str`을 삽입할 수 있다.

 

💡Java에서는 10진수를 n진수로 변환하기 위해 `Integer.toString(int i, int radix)` 메서드를 사용할 수 있다. 해당 메서드는 10진수 `i`를 `radix`진수로 변환한다. 사실 n진수로 변환하기 위한 알고리즘을 따로 작성해줄 필요가 없었다! 하지만 메서드에 너무 의존하기보다는 직접 구현해보는 경험도 중요한 것 같다.

 

n진수는 `t * m` 길이만큼만 계산해주었다. 만약 100번째의 게임 참가자가 1,000개의 숫자를 미리 구하려면 적어도 미리 100 * 1000개의 숫자를 구해놓아야 하기 때문이다.

 

코드

import java.util.*;

class Solution {
    public String solution(int n, int t, int m, int p) {
        // 2~16진법으로 0부터 나열한다.
        // t개의 숫자를 미리 구한다.
        // m명의 인원이 게임을 한다.
        // p번째 인원이 말해야 할 숫자를 구한다.
        
        // n진법을 나열하려면 n을 넘어가면 자릿수를 늘려 진행한다. (이진법은 0, 1, 10, 11, ...)
        // 만약 100번째에 1000개를 미리 구하려면, 100 * 1000의 숫자를 미리 구해 놓는다. 
        StringBuilder sb = new StringBuilder();
        int num = 0;
        // t * m 자리까지 미리 구해 놓는다. 
        while (sb.length() <= t * m) {
            sb.append(decimalToBaseN(num, n));
            num++;
        }
        
        String calculatedNumber = sb.toString();
        StringBuilder answer = new StringBuilder();
        for (int i = 0; i < t; i++) {
            answer.append(calculatedNumber.charAt((p - 1) + i * m)); // p - 1부터 0, m, 2m, ...을 더한다.
        }
        
        return answer.toString();
    }
    
    public static String decimalToBaseN(int decimal, int n) {
        if (decimal == 0) return "0";
        
        StringBuilder sb = new StringBuilder();
        while (decimal > 0) {
            int remainder = decimal % n;
            char digit = (char) (remainder < 10 ? remainder + '0' : 'A' + (remainder - 10));
            sb.insert(0, digit);
            decimal /= n;
        }
        
        return sb.toString();
    }
}