[프로그래머스] 124 나라의 숫자 - Java

문제 설명

 

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

 

풀이 : Success

소스 코드

    public String solution(int n) {
        String base = "412";
        StringBuilder sb = new StringBuilder();
        sb.append(base.charAt(n % 3));
        
        while (n > 3) {
            n = (n-1) / 3;
            sb.append(base.charAt(n % 3));
        }

        return sb.reverse().toString();
    }

 

풀이 회고

우선 124 나라의 숫자의 경우 "1", "2", "4" 총 3개의 숫자로만 표현되므로 삼진법을 구하는 방식과 유사합니다. 이때 십진수를 차례대로 3으로 나누면 다음과 같은 규칙성을 발견할 수 있습니다.

 

십진수(n)	십진수를 3으로 나누었을 때 나머지(n%=3)	십진수를 3으로 나누었을 때 몫(n/=3)
1	1	0
2	2	0
3	0	1
4	1	1
5	2	1
6	0	2
7	1	2
8	2	2
9	0	3

 

우선 십진수를 3으로 나누었을 때 나머지는 첫 번째 숫자 ~ 세 번째 숫자가 하나의 묶음으로 1, 2, 0으로 계속 반복되는 것을 확인할 수 있습니다. 이러한 규칙성을 이용하여 우리는 나머지가 1이면 1로, 나머지가 2면 2로, 나머지가 0이면 4로 표현하면 124 나라의 숫자의 "첫째 자리"는 해결할 수 있을 것으로 보입니다.

 

반면에 십진수를 3으로 나누었을 때 몫은 차례대로 0, 0, 1, / 1, 1, 2, / 2, 2, 3 / ... 처럼 첫 번째 숫자와 두 번째 숫자가 같고 세 번째 숫자는 앞선 두 숫자보다 1이 더 큰 것을 확인할 수 있고 또한 첫 번째 숫자 ~ 세 번째 숫자가 하나의 묶음으로 반복되는 것을 확인할 수 있습니다.

 

이때 세 번째 숫자를 첫 번째 숫자와 두 번째 숫자와 같도록 보정하기 위해 입력받은 십진수 n에서 -1 연산 후에 다시 3을 나누면 몫의 결과가 십진수를 3으로 나누었을 때의 나머지처럼 0, 0, 0 / 1, 1, 1 / 2, 2, 2 / ... 로 마치 3진수 변환에 적합한 형태로 첫 번째 숫자 ~ 세 번째 숫자가 하나의 묶음으로 반복되는 것을 확인할 수 있습니다.

 

여기서 몫이 0이라면 둘째 자리 숫자는 존재하지 않을 것이며, 1이면 둘째 자리 숫자가 1이라는 숫자로 발생해야 하고, 2이면 둘째 자리 숫자가 2라는 숫자로 발생해야하고, 3이면 둘째 자리 숫자가 4라는 숫자로 발생해야할 것입니다.

 

결론적으로 십진수 n이 4 보다 작으면 첫째 자리 숫자만 존재하므로 굳이 몫을 구할 필요 없이 나머지 연산(n % 3)만 하여 해당 나머지 값을 인덱스 용도로 사용해 첫째 자리 숫자의 124 나라 숫자를 구할 수 있을 것입니다. 아울러 십진수 n이 4 이상이면 앞선 방식으로 몫의 결과를 구하고 해당 몫에 대해 나머지 연산(n % 3)을 하여 해당 나머지 값을 인덱스 용도로 사용하면 둘째 자리 이상의 124 나라 숫자를 구할 수 있을 것입니다.

 

 

참고자료

• https://programmers.co.kr/learn/courses/30/lessons/12899