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

1. 예제를 통한 규칙 또는 특징 찾기

  1, 2, 4로 주어진 예제를 통해 수를 조합 한다.

     -1) 1과 2, 5와 6, 7과 8이 124 나라의 수로 변환된 결과 각 1씩 차이가 난다.

     -2) 3의 배수는 4로 끝난다.

     -3) 3n+1번째 수부터  앞 자리 수가 바뀐다.

 

2. 해법 도출

 위 특징들로 미루어 보아 3진법을 사용함을 알 수 있다.

 단, 1, 2, 4만 사용하므로 나머지가 0인 경우 4로 표기한다.

10 진수	124 나라의 숫자	계산 방법
1	1	1*1
2	2	2*1
3	4	(4-1)*1
4	11	(3*1)+(1*1)
5	12	(3*1)+(1*2)
6	14	(3*1)+{1*(4-1)}
7	21	(3*2)+(1*1)
8	22	(3*2)+(1*2)
9	24	(3*2)+{1*(4-1)}
10	41	{3*(4-1)}+(1*1)

 

+) 진법 변환 시 결과를 아래 예시처럼 맨 뒤부터 표기 하므로 코드에서도 기존 문자열 앞에 계산 결과를 더해준다.

    ex) 10진수 숫자 10을 2진법으로 변환할 때

        10 ÷ 2 = 5 ... 0

        5 ÷ 2 = 2 ... 1

        2 ÷ 2 = 1 ... 0

        1 ÷ 2 = 0 ... 1         →     0101이 아닌 1010으로 표기한다.

class Solution {
    public String solution(int n) {
        String[] temp={"4","1","2"};
        String answer = "";
        
        while(n>0){
            int remain=n%3;
            n/=3;
            
            if(remain==0) n--;
            
            answer = temp[remain]+answer;
        }
        return answer;
    }
}

나머지가 0일 때 n-1를 하는 이유

1. n-1을 적용하지 않았을 때

- 1) n = 9
   9%3 = 0 → 4로 표기
   9/3 =3

   n=3
   answer = 4

- 2) n = 3
   3%3 = 0 → 4로 표기
   3/3 =1

   n=1
   answer = 44

- 3) n = 1
   1%3 = 1
   1/3 =0

   n=0
   answer = 144 

144  →  3^2*1+3*(4-1)+(4-1)=9+9+3=21

 

2. n- - 을 적용했을 때

- 1) n = 9
   9%3 = 0 → 4로 표기
   9/3 =3

   n=3-1=2      //코드에서 n--가 적용되는 부분
   answer = 4

- 2) n = 2
   2%3 = 2 
   2/3 = 0

   n=0
   answer = 24

24  →  3*2+(4-1) = 6+3 = 9

위와 같이 n--을 적용해야하지 않을 때의 결과를 검산해보면 잘못된 답임을 알 수 있다.

0을 4로 표기하는 것이 몫에서 3을 빌려온다고 생각하면 이해하기 쉽다.

 

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/12899