[programmers] 124 나라의 숫자
1. 문제 Link
2. 문제 설명
124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다.
- 124 나라에는 자연수만 존재합니다.
- 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 함수를 완성해 주세요.
3. 제한 사항
- n은 500,000,000이하의 자연수 입니다.
4. 입출력 예
| n | result |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 4 |
| 4 | 11 |
5. 코드 해설
5.1. 반복되는 규칙
반복되는 규칙이 있는 것 같습니다. 이를 정리해보고 원하는 답을 얻을 수 있도록 코드를 작성해보도록 하겠습니다.
| 10진법 | 10진법 지수 범위 | 124 나라수(자릿수) | 10진법 | 10진법 지수 범위 | 124 나라수(자릿수) | 10진법 | 10진법 지수 범위 | 124 나라수(자릿수) |
|---|---|---|---|---|---|---|---|---|
| 1 | 3^1 이하 | 1(1) | 6 | (3^2 + 3^1) 이하 | 14(2) | 11 | (3^2 + 3^1) 이하 | 42(2) |
| 2 | 3^1 이하 | 2(1) | 7 | (3^2 + 3^1) 이하 | 21(2) | 12 | (3^2 + 3^1) 이하 | 44(2) |
| 3 | 3^1 이하 | 4(1) | 8 | (3^2 + 3^1) 이하 | 22(2) | 13 | (3^3 + 3^2 + 3^1) 이하 | 111(3) |
| 4 | (3^2 + 3^1) 이하 | 11(2) | 9 | (3^2 + 3^1) 이하 | 24(2) | 14 | (3^3 + 3^2 + 3^1) 이하 | 112(3) |
| 5 | (3^2 + 3^1) 이하 | 12(2) | 10 | (3^2 + 3^1) 이하 | 41(2) | 15 | (3^3 + 3^2 + 3^1) 이하 | 114(3) |
15을 예를 들어 설명해보도록 하겠습니다.
- 15은 27(3^3 + 3^2 + 3^1) 값 이하 12(3^2 + 3^1) 이상입니다.
- 최대 exp 값은 3 입니다. 탐색을 시작하는 base는 12(3^2 + 3^1) 입니다.
- 124 나라에서 3자리인 숫자는 총 27 개가 존재합니다.(27 = 3^exp = 3^3)
- 각 자리 숫자를 지정해보겠습니다. 1, 2, 4 중 하나입니다.
- 첫 번째 숫자를 지정해보겠습니다. 첫 번째 숫자가 증가함에 따라 10진수는 9(3^2)개씩 커집니다.
- 3 값은 9(temp) * 1(subIndex) 보다 작거나 같습니다.(3 = n - base = 15 - 12)
- 맨 앞자리 수는 1(subIndex)가 됩니다.
- base를 12 + 0(9 * 0) 만큼 증가시켜 12을 만듭니다.
- 두 번째 숫자를 지정해보겠습니다. 두 번째 숫자가 증가함에 따라 10진수는 3(3^1)개씩 커집니다.
- 3 값은 3(temp) * 1(subIndex) 보다는 작거나 같습니다.(3 = n - base = 15 - 12)
- 다음 자리 수는 1(subIndex)가 됩니다.
- base를 12 + 0(3 * 0) 만큼 증가시켜 12을 만듭니다.
- 세 번째 숫자를 지정해보겠습니다.
- 3 값은 1(temp) * 3(subIndex) 보다는 작거나 같습니다.(3 = n - base = 15 - 12)
- 다음 자리 수는 3(subIndex)이므로 4가 됩니다.
- base를 12 + 3(1 * 3) 만큼 증가시켜 15을 만듭니다.
6. 제출 코드
class Solution {
public String solution(int n) {
int exp = 1;
int base = 0;
while (n > base + Math.pow(3, exp)) {
base += Math.pow(3, exp);
exp++;
}
StringBuffer answer = new StringBuffer();
for (int index = exp - 1; index >= 0; index--) {
double temp = Math.pow(3, index);
int subIndex = 0;
for (subIndex = 1; subIndex <= 3; subIndex++) {
if (n - base <= temp * subIndex) {
break;
}
}
base += temp * (subIndex - 1);
if (subIndex == 3) {
answer.append(4);
} else {
answer.append(subIndex);
}
}
return answer.toString();
}
}
7. BEST PRACTICE
- 뒤에 자리 수부터 채워나갑니다.
- n이 0이 될 때까지 반복 수행합니다.
- 3으로 나눠 떨어지는 경우 4, 나눠 떨어지지 않는 경우 나머지를 이어 붙입니다.
- 숫자 n을 (n - 1) / 3 만큼 낮춥니다.
class Solution {
public String solution(int n) {
String[] num = { "4", "1", "2" };
String answer = "";
while (n > 0) {
answer = num[n % 3] + answer;
n = (n - 1) / 3;
}
return answer;
}
}
CLOSING
제가 문제를 푼 날은 컨디션이 좋았나봅니다. 오늘의 저는 이해가 안됩니다. 풀어본 문제를 다시 정리해보는 것도 많은 도움이 될 것이라 생각하고 즐거운 마음으로 정리하겠습니다. 규칙을 빠르게 찾아내는 연습과 코드로 옮기는 연습을 열심히 해야겠습니다.
BEST PRACTICE를 보니 정말 감탄밖에 나오지 않습니다.
어떻게 저런 답변이 나올 수 있는지 추리가 되지 않아서 풀이를 찾아보았습니다.
특히 'n = (n - 1) / 3;' 이 분이 어떤 논리를 통해 도출되었는지 정말 놀라울 따름입니다.
3의 배수일 때 다음 자릿수가 1 증가하는게 아니기 때문에 1을 빼주어야 한다.
댓글남기기