코딩테스트: 카카오 기출문제 (n진수 게임)을 풀어보자

https://school.programmers.co.kr/learn/courses/30/lessons/17687

프로그래머스

 

문제에 대한 설명은, 위의 링크로 들어가서 읽어보시길 권장드린다.

문제 자체는 막 어려운 문제는 아니다. 프로그래머스에서도 Lv.2로 지정을 한 만큼, 적당히 패턴이나 방법을 알면 풀 수 있다.

문제는.. 어느 정도 숙련된 사람이라면 가능하다는 것이고, 개개인에 따라서는 어려울 수 있다.

 

문제에서 핵심을 정리하자면 다음과 같다.

1) 지정된 N진수로 0부터 특정 수 까지 생성한다.

2) 특정 수 까지 구한 숫자 중에 특정 인물이 말해야 할 숫자를 t 개를 구한다.

 

여기서 먼저, 가장 필요한 것, 특정 수를 N진법으로 구하는 메소드가 필요하다고 나는 생각했다.

예를 들어 3을 2진법으로 구하라고 하면 [1,1] 이라는 배열로 생성을 하고,

7을 5진법으로 구하라고 하면, [1,2]이라는 배열로 만드는 것이다.

 

 

그런데 문제가 있다.

이 문제는 최대 16진법 까지 구해야 한다고 한다. 

0부터 9까지만 표현이 가능한 현재 10진법으로는 한계가 있으니 이후 숫자는 A, B, C... 등의 알파벳으로 대체하라고 한다.

이를 위해, 나는 문제에서 제시하는 n진법에 맞는 배열을 생성하고자 한다.

        String[] arr = new String[n];
        String[] altArr = {"A", "B", "C", "D", "E", "F"};
        for(int i=0; i < arr.length; i++){
            if(i < 10){
                arr[i] = i + "";
            }else{
                arr[i] = altArr[i-10];
            }
            
        }

문제에서 제시하는 n진법에 맞게 빈 배열을 만든다.

그리고 그 빈 배열을 순회하면서 0 부터 9 까지 넣는다.

만약 n진법이 10을 넘을 경우, 그 이후에는 altArr의 알파벳을 넣는 방식으로 arr를 생성한다.

 

그 다음으로는, N진법을 구하는 메소드를 생성한다.

단, 여기에서는 최대 16진법 까지 표현이 가능한 arr를 인자 값으로 받도록 한다.

예를 들어, 12진법에서 23를 표현할 경우, 기존 메소드에서는 [1, 12]로 표현이 되겠지만,

이를 arr로 치환을 하여 [1, C] 가 되도록 한다.

    public List<String> number(int numberSys, int decimal, String[] arr){
        List<String> arrs = new ArrayList<>();
        while(decimal > 0){
            arrs.add(0, arr[decimal%numberSys]);
            decimal /= numberSys;
        }
        return arrs;
    }

여기서는 무슨 진법인지 numberSys를 넣어야 하며,

구하고자 하는 숫자가 10진법으로 무엇인지 decimal 또한 넣어야 하며,

이후 아까 말한 arr를 넣어야 한다.

 

 

3번째 단계로는, 이 N진법 구하는 number 메소드를 활용해 특정 수 까지의 N진법 수를 구하면 된다.

그럼 특정 수는 어떻게 구하면 되나? 이는 문제에 이미 답이 있다.

미리 구할 갯수 t와 참여하는 인원 m을 곱하면 특정 수가 나오게 된다.

이를 while 문으로 돌려, 특정 수까지 모두 구해지면 루프에서 벗어나도록 구현을 하였다.

        int totalCount = t*m;
        int count = 0;
        List<String> answerList = new ArrayList<>();

        Solution solution = new Solution();      
        answerList.add("0");
        while(answerList.size() < totalCount){
            List<String> result = solution.number(n, count, arr);
            answerList.addAll(result);
            count++;
        }

매 루프마다 count, 즉 10진법 수가 1씩 늘어난다. 그리고 solution.number로 N진법 수를 구한다.

이를 answerList의 배열에 추가를 하고, 다음 루프에서 answerList.size()로 특정 수인 totalCount를 넘었는지 확인한다.

 

 

자, 이제 마지막이다. 특정 수까지의 수는 다 구했다.

이제 튜브의 순서 p, 즉 p번째 사람이 말해야 할 숫자를 t만큼 구하면 된다.

이는 for 문으로 해당 배열을 순회하면서 찾아내, answer문자열에 넣는 식으로 구했다.

        String answer = "";
        for(int i = 0; i < t; i++){
            int arrPos = p-1 + i*m;
            answer += answerList.get(arrPos);
        }
        return answer;

 int arrPos = p-1 + i*m; 이것이 생각보다 중요하다. 왜냐하면 배열은 0번째 부터 시작을 하니까...

 

 

총 코드는 다음 아래와 같다.

나보다 쉽게 고작 열 몇 줄로 풀어버린 사람도 있고, 쉽게쉽게 설명하시는 분들도 계시니 많은 자료 참고를 부탁드린다.

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List; 

class Solution {
    public String solution(int n, int t, int m, int p) {
        String[] arr = new String[n];
        String[] altArr = {"A", "B", "C", "D", "E", "F"};
        for(int i=0; i < arr.length; i++){
            if(i < 10){
                arr[i] = i + "";
            }else{
                arr[i] = altArr[i-10];
            }
            
        }
        int totalCount = t*m;
        int count = 0;
        List<String> answerList = new ArrayList<>();

        Solution solution = new Solution();      
        answerList.add("0");
        while(answerList.size() < totalCount){
            List<String> result = solution.number(n, count, arr);
            answerList.addAll(result);
            count++;
        }

        String answer = "";
        for(int i = 0; i < t; i++){
            int arrPos = p-1 + i*m;
            answer += answerList.get(arrPos);
        }
        return answer;
    }
    
    public List<String> number(int numberSys, int decimal, String[] arr){
        List<String> arrs = new ArrayList<>();
        while(decimal > 0){
            arrs.add(0, arr[decimal%numberSys]);
            decimal /= numberSys;
        }
        return arrs;
    }
}

 

 

그럼 안녕~~~