문제 설명
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 함수를 완성해 주세요.
제한사항
•
n은 50,000,000이하의 자연수 입니다.
입출력 예
n | result |
1 | 1 |
2 | 2 |
3 | 4 |
4 | 11 |
나의 풀이
import java.util.*;
class Solution {
public String solution(int n) {
StringBuilder sb = new StringBuilder();
int exp = 1;
while (n > 0) {
int mod = (int) Math.pow(3, exp);
int temp = n % mod;
temp = (temp == 0) ? mod - 1 : temp - 1;
temp /= (int) Math.pow(3, exp - 1);
sb.append(mapper(temp));
n -= mod;
exp++;
}
sb.reverse();
return sb.toString();
}
String mapper(int n) {
switch(n) {
case 0: return "1";
case 1: return "2";
case 2: return "4";
}
return "0";
}
}
Java
복사
Remark
•
처음에 단순 3진법 문제인 줄 알았는데 0이 없는 3진법이라는 특이한 케이스여서 이해하기 힘들었음
•
풀이 아이디어
◦
124는 헷갈리니까 abc로 바꿔 생각함
이진수 변환수 3진법
0 0
1 a 1
2 b 2
3 c 10
4 aa 11
5 ab 12
6 ac 20
7 ba 21
8 bb 22
9 bc 100
10 ca 101
11 cb 102
12 cc 110
13 aaa 111
14 aab 112
15 aac 120
16 aba 121
17 abb 122
18 abc 200
19 aca
20 acb
...
39 ccc
Java
복사
◦
위 패턴을 보면
▪
첫째 자리는 1부터 시작해 [abc] [abc] [abc] …
▪
둘째 자리는 4부터 시작해 [aaa bbb ccc] [aaa bbb ccc] …
▪
셋째 자리는 13부터 시작해 [aaa aaa aaa bbb bbb bbb ccc ccc ccc] …
처럼 자리수가 올라갈 때마다 , , 간격으로 abc가 번갈아 나옴
◦
맨 처음 으로 나머지 연산을 했을 때 0, 1, 2 중 하나로 상대적인 위치를 알게 되어 abc 판별
◦
n에서 을 빼줌. 위를 보면 n=4부터 둘째자리 패턴이 시작되기 때문
▪
으로 나머지 연산을 시행해 0, 1, 2, 3, 4, 5, 6, 7, 8 중 하나로 상대적인 위치를 구함(aaa bbb ccc)
•
해보면 나머지 연산 시행 후 결과값이 1부터 시작함.
나머지가 차례대로
1, 2, 3, 4, 5, 6, 7, 8, 0 이 되기 때문에 1씩 빼주고, 0인 경우는 8로 만들어서
0, 1, 2, 3, 4, 5, 6, 7, 8 로 정돈
▪
그다음 으로 나누면 0, 0, 0, 1, 1, 1, 2, 2, 2 처럼 소속된 구획을 알 수 있음
◦
3의 승수를 높여가며 n이 0보다 작아질 때까지 위의 과정을 반복함
•
다른 분들의 풀이
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;
}
}
Java
복사
◦
심플하고 효율적인 풀이
▪
일단 매핑을 메서드가 아니라 배열로 해도 됐음
▪
n을 3으로 나눠서,
…aaaaaaaaabbbbbbbbbccccccccc → aaabbbccc → abc 처럼 n이 한 구간씩 내려옴
▪
다만 이 과정에서 원래라면
(0 1 2) (3 4 5) (6 7 8) → 0 1 2
처럼 내려와야 하지만 위의 경우 n이 1부터 시작하면서 abc와 패턴을 같이 하기 때문에
(1 2 3) (4 5 6) (7 8 9) 처럼 돼버림. 따라서 1씩 빼주고 3으로 나눠야 정확한 구간으로 내려옴