프로그래머스 - 124나라의 숫자 JS

문제 개빡침

문제

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

124 나라에는 자연수만 존재합니다.
124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다.
예를 들어서 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이하의 자연수 입니다.

접근법

처음에는 4 + 1 => 11로 넘어가는 걸 이용해서 1부터 n까지 구해보려 했으나 효율성 테스트까지 통과해야 되기 때문에 1부터 n까지 반복문 돌리는건 안되는듯.
옛날에 ncs 공부할 때 10진법을 n진법으로 바꾸는 문제같은거 보면 나눠서 나머지랑 몫이랑 이용해서 바꾸는걸 본 기억이 있어서 찾아보니까
3으로 나눠서 몫 + 나머지로 나타내면 되는데,
4 / 3 = 1 , 4 % 3 = 1 => 4는 11
6 / 3 = 2, 6 % 3 = 0 => n이 3으로 나누어 떨어지는 경우에는 정확하진 않지만 나머지가 0으로 나오면 4로 나타내야 하고, 몫은 -1을 해줘야 되나? 라는 생각을 하게 됨
그래서 n을 구하기 위해서 n / 3의 값까지는 구해야 되니 반복문을 돌려봤는데, 정답은 맞는데 효율성에서 통과를 못함

풀이

44라는 수가 있으면 몫:14 나머지:2인데, 이 14라는 수를 구해서 제일 뒤에 2를 붙여주면 구한다는 건 알겠음

• 14는 또 몫:4 나머지:2인데 4라는 수를 구해서 2를 붙여주면 됨
• 4는 몫:1 나머지:1이니 11이라는 수가 나오고, 14는 11에 2를 붙여서 112고, 44는 112에 2를 붙여서 1122가 됨
  한마디로 n이 3보다 작아질때까지 계속 나눠주면 되는데
  문제는 n이 3의 배수일때임(이게 개빡침)
• 45(몫:15,나머지:0) -> 15 + 4 붙여줌
• 15(몫:5,나머지:0) -> 5 + 4 붙여줌
• 5(몫:1,나머지:2) -> 12
  이제 거슬러 올라가면 1244가 답이냐? 아님...
• 위에서 했던 -을 해줘야됨
• n을 나눴을 때 3으로 나누어 떨어진다? 나머지는 4를 붙여주고, 그 다음으로 계산할 n/3에 -1을 해서 보내줘야 함
  이렇게 알고보면 쉬운데... n을 한번만 -1 해주면 되는거 아닌가?(테케는 가능) 해서 계속 그렇게 구했더니 다틀려서...

코드

function solution(n) {
    const arr = ['4','1','2','4']
    const str = []
    if(n<=3){return arr[n]}
    while(n > 3){
        if(n % 3 === 0){
            str.unshift(arr[n%3])
            n = Math.floor(n/3)-1
        } else {
            str.unshift(arr[n%3])
            n = Math.floor(n/3)
        }
    }
    str.unshift(arr[n])
    return str.join('')
}

코드만 보면 참 쉬움
한번 할때마다 나머지를 배열 앞쪽부터 채우면서, 마지막에 n이 3보다 작아질때 그 몫을 넣어주면서 join으로 마무리