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

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

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

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

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

10진법124 나라10진법124 나라

1	1	6	14
2	2	7	21
3	4	8	22
4	11	9	24
5	12	10	41

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

2. 입력

• n은 500,000,000이하의 자연수 입니다.

3. 예제

n	result
1	1
2	2
3	4
4	11

4. 풀이

124의 숫자만 사용할 수 있는 경우는 진법을 생각해보면 쉽게 접근이 가능합니다.

 

우리가 쓰는 0~9까지의 숫자는 10진법의 숫자입니다. 즉 열개의 숫자를 이용하는 방법을 말합니다.

 

컴퓨터가 쓰는 2진법은 0과 1 두 개의 숫자를 이용하는 방법을 말합니다.

 

그럼 숫자 3개를 이용하는 124의 경우는 몇 진법을 이용하면 될까요?

 

바로 3진법을 이용하면 숫자 3개를 이용하여 접근할 수 있습니다.

 

그런데 문제는 3진법은 0, 1, 2 숫자를 이용하지만 문제는 1, 2, 4 숫자를 이용한다고 되어 있습니다.

 

즉 3진법과 다른 점은 0이 아닌 4를 사용한다는 점입니다.

 

먼저 10진법 숫자를 X진법으로 변환하는 방법을 알아보겠습니다.

 

10진법의 숫자를 나눈 나머지 값을 나열하고 마지막 몫부터 시작하여 역순으로 수를 만들면 됩니다.

 

예를 들어 10진법 14를 3진법으로 변경해 보겠습니다.

1. 14를 3으로 나눈 몫과 나머지를 찾습니다. 몫은 4이고 나머지는 2가 됩니다.
2. 4를 3으로 나눈 몫과 나머지를 찾습니다. 몫은 1이고 나머지는 1이 됩니다.
3. 몫이 3보다 작으므로 마지막 몫부터 역순으로 숫자를 이어 붙입니다.
4. 최종 10진법 14의 3진법은 112가 됩니다.

그럼 Java 코드를 이용하여 10진법을 3진법으로 만드는 코드를 확인해 보겠습니다.

 

StringBuilder answer = new StringBuilder();

while (n > 0) {
	answer.insert(0, n % 3);

	n = n / 3;
}

return answer.toString();

위 코드가 10진법을 3진법으로 변경하는 방법입니다.

 

그럼 이제 문제로 돌아가 124의 수로 10진법을 나타 내는 방법을 알아보도록 하겠습니다.

 

위의 진법 변환처럼 3진법으로 변환을 하고 0과 4가 다르니 0을 4로 치환하면 된다고 생각할 수 있습니다.

 

하지만 작은 차이가 있습니다. 3진법의 경우 계산 과정에서 3의 배수이면(나머지가 0이 되면) 자릿수 값이 변경되게 됩니다.

 

• 10진법 3을 3진법으로 변환하면 0이 아닌 10이 되게 됩니다.
  0을 4로만 치환하게 된다면 14가 되어 정답이 될 수 없습니다.
  
  
• 10진법 6을 3진법으로 변환하면 10이 아닌 20이 되게 됩니다.
  0을 4로만 치환하게 된다면 24가 되어 정답이 될 수 없습니다.

이제 마지막 과정은 3진법으로 변환하는 과정 중 3의 배수가 나왔을 경우 앞 자릿수의 값이 1 증가하지 않도록 해야 됩니다.

 

위 과정처럼 3의 배수인 경우 앞 자릿수의 값의 변경을 막기 위해 나머지가 0이 되면 나머지가 3이 되도록 만들어야 합니다.

 

즉 3진법에서 0, 1, 2의 숫자를 이용하여 표현하던 것을 1, 2, 3의 숫자를 이용하여 표현하도록 변경하는 것입니다.

 

1, 2, 3을 이용한 3진법을 만들기 위해서는 3의 배수인 경우 몫에서 1을 빼고 나머지를 0에서 3으로 만들어 주면 1, 2, 3을 이용한 3진법이 완성됩니다.

• 15를 1, 2, 3진법으로 변환
  

  

  15를 3으로 나눈 몫 5에서 1을 빼고 나머지를 3으로 변경하였습니다.
  4를 3으로 나눈 몫 1과 나머지 1이 되어 1, 2, 3진법은 113으로 변환됩니다.
  
  
• 24를 1, 2, 3진법으로 변환
  

  

  24를 3으로 나눈 몫 8에서 1을 빼고 나머지를 3으로 변경하였습니다.
  7을 3으로 나눈 몫 2와 나머지 1이 되어 1, 2, 3진법은 213으로 변환됩니다.
• 21을 1, 2, 3진법으로 변환
  

  

  21을 3으로 나눈 몫 7에서 1을 빼고 나머지를 3으로 변경하였습니다.
  6을 3으로 나눈 몫 2에서 1을 빼고 나머지를 3으로 변경하였습니다.
  마지막 몫이 3보다 작으므로 1, 2, 3진법은 133으로 변환됩니다.

이제 3진법 변경 과정에서 3의 배수가 나오더라도 앞 자릿수의 값이 1 더해지는 것을 제거하였습니다. 이제 1, 2, 3진법에서 3을 4로만 변경하면 124 나라의 숫자로 만들 수 있습니다.

 

위 과정을 정리하면 3진법의 계산 과정 중 3의 배수가 나오면 나머지 값 0을 4로 변경하고 몫의 값에서 -1을 하여 앞자리 숫자 값 추가를 방지하여 계산하면 문제를 풀 수 있습니다.

 

5. 코드

전체 코드는 Git에 있습니다.

StringBuilder answer = new StringBuilder();

while (n > 0) {
	answer.insert(0, n % 3 == 0 ? 4 : n % 3);
	if (n % 3 == 0)
		n = n / 3 - 1;
	else
		n = n / 3;
}

return answer.toString();