124나라의 숫자

코딩테스트 연습 - 124 나라의 숫자 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 124 나라의 숫자

 

풀이)

접근)

우선 경우의 수는 자리 수별로 3의 거듭제곱만큼 늘어난다.

 n을 3으로 나눠서 (몫, 나머지)로 묶어보았더니 (0,1) (0,2) (1,0) | (1,1) (1,2,) (2,0) 이런식으로 나열이 되었다.

나머지 값이 (1,2,3)으로 끊기면 좋을것 같아서 n % 3 의 나머지가 0일 경우 몫에다가 몫-1값을 넣고 나머지에는 3을 넣어주었더니 아래와 같은 결과가 나왔다.(몫이 3보다 클 경우에는 한번 더 분해한다)

(0,1) (0,2) (0,3)
(1,1) (1,2) (1,3) | (2,1) (2,2) (2,3) | (3,1) (3,2) (3,3)
(4,1)  -> (1,1,1) | (4,2) -> (1,1,2)  | (4,3) -> (1,1,3)
(5,1)  -> (1,2,1)
(6,1)  -> (1,3,1)
(7,1)  -> (2,1,1)
(8,1)  -> (2,2,1)
(9,1)  -> (2,3,1)
(10,1) -> (3,1,1)
(11,1) -> (3,2,1)
(12,1) -> (3,3,1) 
(13,1) -> (4,1,1) -> (1,1,1,1) 

알고리즘) 

1. 위와 같은 방식으로 n의 몫과 나머지를 구한다.
2. 나머지 값과 매칭되는 값을 문자열 answer에 추가한다.
3. 몫이 0일 경우 종료한다.
4. 몫이 1~3일 경우 몫과 매칭되는 값을 문자열에 추가한다.
5. 몫이 3보다 클 경우 몫을 n에 대입해주고 위 과정을 반복한다.

코드

class Solution {
    public String solution(int n) {
                String answer = "";
        int div = -1, mod = -1;
        while(true)
        {         
            if(n % 3 == 0)
            {
                div = n/3 - 1;
                mod = 3;              
            }
            else{
                div = n/3;
                mod = n%3;
            }
            //System.out.printf("div : %d mod : %d\n",div, mod);
            if(mod == 1)
                 answer = "1"+ answer ;
            else if(mod == 2)
                 answer = "2"+ answer ;
            else if(mod == 3)
               answer = "4"+ answer ;
            if(div == 0)
                break;
            else if(1 <= div && div <= 3)
            {
                 if(div == 1)
                    answer = "1"+ answer ;
                 else if(div == 2)
                    answer = "2"+ answer ;
                 else if(div == 3)
                    answer = "4"+ answer ;
                 break;
            } 
                n = div;
        }

        return answer;
    }
}