문제
문제 설명
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 함수를 완성해 주세요.
제한사항
- n은 500,000,000이하의 자연수 입니다.
입출력 예
| n | result |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 4 |
| 4 | 11 |
Approach #1
1 : 1
2 : 2
3 : 4
4 : 11 -> 1에서 가져옴
5 : 12
6 : 14
7 : 21 -> 2에서 가져옴
8 : 22
9 : 24
10: 41 -> 3에서 가져옴
11: 42
12: 44
13: 111 -> 4에서 가져옴
14: 112
15: 114
16: 121 -> 5에서 가져옴
table 구성
0 1 2 3 4 5 6 7 8 9 10
0 1 2 4
^
만약 9를 찾고 싶다. 1부터 9까지 table을 돈다.
인덱스 123은 124로 채워넣고, pointer를 인덱스 1로.
인덱스 i%3===1이면 포인터 숫자+ 1
2이면 포인터 숫자+ 2
0이면 포인터 숫자 +4, 포인터++
n 크기 + 1 만큼의 배열을 만들어서, 인덱스=10진수, 해당 인덱스의 배열값=124 나라의 수 라고 생각했다. 인덱스 123의 값은 124로 초기 셋팅 해주고 for문으로 4부터 n까지 돌며 n까지의 모든 124나라의 수를 구하는 방식.
Solution #1 (효율성 테스트 통과 X 😭)
function solution(n) {
let nArr = [];
nArr[0] = "0";
nArr[1] = "1";
nArr[2] = "2";
nArr[3] = "4";
let p = 1;
for(let i=4; i<=n; i++){
if(i%3 === 1) nArr[i] = nArr[p]+"1";
if(i%3 === 2) nArr[i] = nArr[p]+"2";
if(i%3 === 0){
nArr[i] = nArr[p]+"4";
p++;
}
}
return nArr[n];
}Time Complexity
O(N)
for문에서 4부터 N까지 도니까 정확히는 O(N-3) -> O(N)
Space Complexity
O(N)
길이가 N+1인 배열 생성하기 때문에 O(N+1) -> O(N)
Review
이전값을 참조해서 n을 새롭게 만드는 거지만... 제한사항에서 n이 5억까지 될수 있다고 하니.. 만약 n이 5억이면,,,(끔찍)
테스트케이스는 전부 통과했지만 효율성 테스트에서 통과하지 못했다. ㅠㅠ....
결국 힌트 참고해서 2번째 시도..
- 제한사항 잘 확인하고, 시간복잡도 고려해서 코드 작성하자!
Approach #2
----
3진법
012로..
124
0: 0
1: 01 /1
2: 02 /2
3: 10 /4
4: 11 /11
5: 12 /12
6: 20 /14
7: 21 /21
8: 22 /22
9: 30 /24
3으로 나누어 떨어지면 몫-1 해주고 나머지3
3일때 ->4로 바꿔줌
//11 -> 42
3 11
3 3 2
0 3
//15->114
3 15
4 3
1 1
나머지가 0이 나오면
몫-1해주고 나머지 3
//16->121
3 16
5 1
1 2
힌트를 봤는데도 풀이에 옮기기까지 시간이 꽤나 걸렸다.
3진법을 이용해서 풀면 되는 문제인데..
일반적인 3진법이 0,1,2를 이용하니까 124 나라에서는 1,2,4로 표현하면 되는거 아닌가?
간단하게 생각하면 이렇다. 그런데... 그렇게 간단하지가 않다.
일단 124 나라에서는 0을 표현할 방법이 없다.
예시로 9라는 10진수를 변환해보자.
일반적인 3진법에서 9:
9/3 = 3 ... 0
3/3 = 1 ... 0
-> 100 으로 변환된다.
하지만 124 나라에서 9는 "24"로 변환된다.
나머지가 0이 됐을때의 처리가 필요한 것이다.
그렇기에 나머지가 0인 경우는 몫-1을 해주어 나머지를 3으로 만들어줘야 한다.
124 나라에서의 9: "24"
9/3 = 3 ... 0
-> 나머지가 0이기 때문에 몫-1해주어 나머지를 3으로 만들어준다.
9/3 = 2 ... 3
-> 이 상태에서 변환하면 "23"이 되는데, 124 나라에서 3이라는 수는 존재하지 않는다.
그렇기에 나머지 3은 4로 치환해야한다.
-> 9/3 = 2 ... 3 -> 4로 치환.
-> 우리가 원하는 "24"가 도출된다.
예시) 124 나라에서의 10진수 15: "114"
15/3 = 5 ... 0
-> 나머지가 0이기 때문에 몫-1 해주어 나머지를 3으로 만들어준다.
15/3 = 4 ... 3 -> 4로 치환
4/3 = 1 ... 1
-> 나머지 3은 4로 치환해주어 정답인 "114"가 도출된다.
예시) 124 나라에서의 10진수 11: "42"
11/3 = 3 ... 2
3/3 = 1 ... 0
-> 나머지 0이기 때문에 몫-1 해주어 나머지를 3으로 만들어준다.
3/3 = 0 ... 3 -> 4로 치환
-> "042" 가 도출되지만 맨 앞에 0이 올수 없기 때문에 코드에서 몫이 0인 경우는 처리하지 않도록 한다.
-> 정답인 "42" 도출
Solution #2
function solution(n) {
let res = "";
res = dfs(n, res);
return res;
}
function dfs(n, res) {
let tempQ = parseInt(n / 3);
let tempR = n % 3;
if (tempR === 0) {
tempQ = tempQ - 1;
tempR = 3;
}
if (tempQ >= 3) {
res = dfs(tempQ, res);
}
if (tempR === 3) tempR = 4;
if (tempQ < 3 && tempQ !== 0) res += tempQ.toString();
res += tempR.toString();
return res;
}N: n.length
R: res.length
Time Complexity
O(logN)
Space Complexity
O(R)
Review
- 효율성 테스트가 빡셌다.. 이거 레벨 2 문제 맞냐구 ㅠㅠㅠㅠ
TIL
- 정수로 숫자 바꾸고 싶을때는 num = parseInt(num).
Solution #3
function change124(n) {
var src = [4,1,2];
var result = '';
while(n) {
result = src[n%3] + result;
n = Math.floor((n-1)/3);
}
return result;
}프로그래머스에서 줍줍해온 코드인데 보자마자 미쳤다고 생각했다.
3진법을 인덱스로 변환한 접근... ^.^ 세상에 천재가 참 많구나..
n=15 일때를 생각해보면..
n = 15
result = 4 + ""
n = 4
result = 1 + "4"
n = 1
result = 1 + "14"
n = 0 -> break;
return "114" <- 정답.
N: n.length
R: result.length
Time Complexity
O(logN)
Space Complexity
O(R)
