[프로그래머스/JavaScript] 점프와 순간 이동

https://school.programmers.co.kr/learn/courses/30/lessons/12980

프로그래머스

---

1) 풀이

이 문제도 며칠간을 끙끙대다가 겨우 풀었는데 생각해보면 좀 어이없다..

일단 나는 우선 이 문제를 자료형 Map 을 이용해서 key에 현재 있는 칸, value에 건전지 사용량을 저장했었다

Map 을 하나 만들어서 재귀함수를 이용해서 값을 넣어주고 그다음 값은 재귀로 또 보고 또 보고.. 이런 식으로 진행했으나

자바스크립트는 재귀의 깊이가 한정되어 있기 때문에 오류가 떴다

그래서 재귀함수를 사용하지 않기 위해, 재귀함수 내의 로직들을 밖으로 빼내고 Map에서 배열로, 즉 2차원 배열로 똑같이 저장하고 탐색해보려 했다! (Map 자료형의 특성상 index로 접근이 불가한데, 탐색하기가 너무 번거롭기 때문)

로직은 다음과 같다.

처음에 어차피 1만큼을 가야 점프든, 순간이동이든 할 수 있기 때문에 [1, 1] 를 기본적으로 집어넣어준다

그리고 그 배열에서 첫번째 요소를 shift()로 빼낸 다음, 이 요소에서 x2 하여 순간이동한 값과 건전지 사용량(현재는 첫번째 칸 기준이기 때문에 1), 그리고 +1 해서 +1된 건전지 사용량 모두를 배열에 넣어준다. 그리고 또 다시 다음 첫번째 요소를 shift() 해서 똑같은 과정을 진행하되, 특정 칸 값이 이미 배열에 존재하면 건전지 사용량을 비교하여 더 작은 값을 넣어주곤 했다. 그렇게 해서 만들어진 반복문 로직은 다음과 같다

  while(gone.length!==0){ //gone은 값을 저장하는 2차원 배열 . 해당로직은 결과적으로 필요없다
        cur=gone.shift();
        if(cur[0]===n) return cur[1];
        if(cur[0]>n) continue;
        if(cur[0]*2===n) return cur[1];
        if(cur[0]+1===n) return cur[1]+1;
       tmp=gone.findIndex((e)=>e[0]===cur[0]*2);
        if(tmp!==-1){
            if(gone[tmp][1]>cur[1]) gone[tmp][1]=cur[1];
        }else gone.push([cur[0]*2,cur[1]]);
        tmp=gone.filter((e)=>e[0]<=cur[0]&&e[1]<=cur[1]);
        if(tmp.length!==0) continue;
        if(cur[0]*2!==cur[0]+1){
        tmp=gone.findIndex((e)=>e[0]===cur[0]+1);
        if(tmp!==-1){
             if(gone[tmp][1]>cur[1]+1) gone[tmp][1]=cur[1]+1;
        }else gone.push([cur[0]+1,cur[1]+1]);
        }
    }

해당 로직을 돌았더니 정답은 다 나오는데, 시간초과가 여전히 나왔다.

혹시 n이 너무 커서 오래 걸리나? 하는 생각에 n을 n%2가 0이 아닐 때까지 2로 나눠주는 반복문을 저 반복문 앞에 넣어줬다. 나의 생각은, 어차피 x2로 순간이동을 하고, n%2가 0이 아닌 순간에는 1칸 앞으로 가야하는 타이밍일텐데, 그때부터 내가 저 로직을 사용하면 되겠다는 생각이었지만.. 사실 그렇게 따지면 이것만 이용하면 저 로직 필요없이 정답을 구할 수 있다..! 이거를 이 새벽에서야.. 몇날 며칠 고민하다가 떠올리게 되었다.

 

혹시나 해서 다 지워봤더니.. 어처구니 없이 정답이었다

오늘도 삽질했지만.. 그래도 한 문제 맞혔으니까 😂 

2) 최종 소스코드

function solution(n)
{  
    let count=0;

    while(n!==0){
        if(n%2!==0) count++;
        n=Math.floor(n/2);
    }
    return count;

}