프로그래머스 Lv.2) n진수 게임

2018 KAKAO BLIND RECRUITMENT [3차]

n진수 게임

코딩테스트 연습 - [3차] n진수 게임

풀이

개인적으로는 가장 어려운 문제였다. 오랫동안 풀지 못해서 카카오 해설을 봤는데 정답률이 96%정도..? 된 것 같았다. 마음이 아프다...

어떻게 해야 효율적일지, 수학식을 생각하다가 시간을 보내고 머리가 복잡해지면서 지친 것같다.

도저히 안되겠길래 문제 풀이 포스팅을 찾아보았는데, 최대가 16진수니까 16진수에 맞춰 미리 char 배열을 만들어 두고, 최대 경우의 숫자까지 모두 다 String에 더해주는 것을 보았다. 처음에 이를 생각했는데 비효율적이라고 생각해서 이리저리 생각하다가, 까먹었었다...

아무튼 이 풀이가 된다는 것을 보고 이 로직을 이용해 코드를 작성했다.

 

미리 구할 숫자의 갯수 t X 게임에 참가하는 인원 m 에서 1을 뺀 숫자가 매 게임마다 나올 수 있는 최대 수이다.

t는 튜브가 말해야하는 횟수고, 게임 참가인원이 m이니까, m번을 돌아야 튜브의 차례가 다시 돌아오기 때문이다. 그리고 이 게임은 0부터 시작하기 때문에 1을 뺀 수가 최대 수이다.

 

입력받은 N진수에 따라 N진법 문자열을 리턴해주는 getNumString 메소드를 만들었다. 입력받은 숫자를 N으로 나눈 값이 0이 아닐때 까지 while문을 돌면서 진법에 따라 StringBuffer에 붙여주었다. 이 때, 미리 생성해둔 16진수에 따른 char 배열에서 값을 가져왔다.

받아오는 인덱스 값은 숫자에서 N으로 나눈 나머지 값으로 불러왔다. 진수 만드는 과정을 생각해보면 금방 이해가 될 것이다.

또한, 16진수보다 작은 진수라면 index가 최대 N-1까지 밖에 가지 못할 것이기 때문에 16진수에 따른 char 배열 하나만 있어도 된다.

 

N진법에 따라 다 붙여준 다음에 StringBuffer의 reverse() 메소드를 이용해 문자열을 뒤집어 주었다.

왜냐하면, 숫자를 N으로 나누면서 남은 수를 저장할 때, 맨 뒤에서부터 앞으로 붙여주어야 하는데 StringBuffer에는 뒤에 붙이는 append 메소드밖에 없기 때문이다.                 그냥 String의 concat 메소드를 이용해서 앞에 붙여도 무관할 것 같기는 하다.

 

0 ~ 최대 숫자까지 N진법으로 바꾸면서 하나의 문자열에 저장했다. 이후, 튜브가 말해야하는 차례의 숫자를 돌면서, 해당 index에 저장된 문자를 하나씩 더해 답을 구했다.

 

로직

1. 게임에서 말할 수 있는 최대 숫자까지 for문을 돌면서, N진법으로 바꿔 String을 계속해서 붙여준다.

2. 모든 숫자를 저장한 String에서 튜브가 말하는 차례에 말해야하는 문자를 for문을 통해 저장해준다.

3. 저장된 String을 리턴해준다.

 

코드

class Solution {
    char[] DIGIT_CH = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
    
    public String solution(int n, int t, int m, int p) {
        StringBuffer sb = new StringBuffer();
        StringBuffer result = new StringBuffer();
        for(int num=0; num<t*m; num++) {    // 최대 경우의 수 만큼 숫자를 돌면서
            sb.append(getNumString(num, n)); // N진법으로 변환한 수를 String에 붙여준다.
        }
        for(int turn=0; turn<t; turn++) {
            int idx = turn*m+p-1; // 튜브가 말하는 차례 idx
            result.append(sb.charAt(idx));  // 미리 만들어둔 전체 순서에서 튜브가 말할 숫자 가져온다
        }
        return result.toString();
    }
    
    private String getNumString(int num, int digit) {         
        StringBuffer sb = new StringBuffer();               
        while(num/digit!=0) {
            int idx = num%digit;
            sb.append(DIGIT_CH[idx]);
            num /= digit;
        }
        sb.append(DIGIT_CH[num%digit]);
        sb.reverse();
        return sb.toString();
    }
}