[프로그래머스] Lv.2 124 나라의 숫자 (Java)

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

프로그래머스

 

문제 설명

124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다.

1. 124 나라에는 자연수만 존재합니다.

2. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다.

예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다.

자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution함수를 완성해 주세요.

 

제한사항

- n은 50,000,000 이하의 자연수입니다.

---

💡 아이디어

자릿수와 해당 자릿수의 개수를 보면서 규칙을 찾는다.

자릿수가 1인 수들은 모두 3개로 3^1개

자릿수가 2인 수들은 모두 9개로 3^2개

... 따라서 자릿수가 k인 수들은 모두 3^k개라는 것을 알 수 있다.

 

n의 자릿수를 구하고, 해당 자릿수의 몇 번째 숫자인지 구한다.

 

그리고 모든 수를 표현할 때 1, 2, 4만을 가지고 표현하는 것은 3진법에서 0, 1, 2만을 사용하는 것과 비슷하다.

n의 자릿수를 구하고 몇 번째 숫자인지 구했다면 몇 번째 숫자인지 나타내는 숫자를 3진법으로 바꿔 

0=>1, 1=>2, 2=>4로 변환해 answer을 구한다.

 

📗 풀이과정

1. n의 자릿수와 해당 자릿수에서 몇 번째 숫자인지 구합니다.

int digit=1; //자릿수
int cnt=0; //digit 자릿수에서 몇 번째 숫자인지

while(true){
	if(n<=Math.pow(3,digit)){//다음자릿수를 넘어가지 않는 경우
    	cnt=n-cnt;break;//몇번째 숫자인지 저장
        
    }else{//다음자릿수로 넘어가는 경우
    	n-=Math.pow(3,digit);
        digit++;//자릿수 하나 늘린다
    }
}

 

2. 해당 숫자가 몇 번째 인지 구했다면, 숫자 0을 사용하지 않기 때문에 3진법으로 바꿀 때에도 cnt-1을 3진법으로 바꿔준다. (몇 번째 숫자인지는 1번부터 시작하기 때문에 0번부터 시작하는 걸로 만들어주는 것.)

//몇 번째 숫자인지 구했다면 -1을 해서 3진법으로 바꿈
String base3 = Integer.toString(cnt-1,3);

 

3. 자릿수를 모두 채우기 위해 숫자의 앞자리를 모두 0으로 채워줍니다.

while(base3.length()!=digit) base3="0"+base3;//자릿수 채움

 

4. 3진법으로 바꾼 숫자를 0:1, 1:2, 2:4로 바꿔주고, 구한 answer을 return 합니다.

for(int i=0;i<base3.length();i++){// 0:1, 1:2, 2:4 대입
	if(base3.charAt(i)=='0') answer+="1";
    else if(base3.charAt(i)=='1') answer+="2";
    else answer+="4";
}

---

전체 코드

class Solution {
    public String solution(int n) {
        String answer = "";
        
        int digit=1;//자릿수
        int cnt=0;//digit 자릿수에서 몇번째 숫자인지
        
        while(true){
            if(n<=Math.pow(3,digit)){
                cnt=n-cnt;break;
            }else{
                n-=Math.pow(3,digit);
                digit++;
            }
        }
        //System.out.println(digit+" "+cnt);
        
        String base3=Integer.toString(cnt-1,3);//몇번째 숫자인지 구했다면 -1을 해서 3진법으로 바꿈.
        while(base3.length()!=digit) base3="0"+base3;//자릿수를 채우기 위해 0 더해줌.
        
        //System.out.println(base3);
        
        for(int i=0;i<base3.length();i++){// 0:1, 1:2, 2:4 대입
            if(base3.charAt(i)=='0') answer+="1";
            else if(base3.charAt(i)=='1') answer+="2";
            else answer+="4";
        }
        
        return answer;
    }
}