[프로그래머스] level.2 점프와 순간 이동

 

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

프로그래머스

 

---

나의 풀이 

function solution(n){
    let result = 1 // 무조건 처음에 점프 한 번은 해줘야한다.
    while(n > 1){
        if(n%2 === 0) n /= 2
        else{
            n -= 1
            result++
        }  
    }
    return result;
}

 

처음에는 감이 안 잡혔는데 

역시 몇번 대입해봐야 뭔가가 보인다.

n = 4 일때는

  1  2 2  result = 1 이다. 

n = 5 일때는 

  1  2  2  1  result = 2 이다.

 

n= 6 일때는 

  1  2  1   2    result = 2 이다. 

 

n = 7 일때는 

  1 2 1 2 1     result = 3이다. 

 

n = 8 일때는 

  1 2 2 2       result = 1이다. 

n = 9 일때는 

 1 2 2 2 1   result = 1이다.

 

n = 10 일때는

1 2 2  1 2    result  = 2 이다. 

 

 

나열하면서 느꼈다.  아 홀짝으로 나누면 뭔가 보이겠구나 

가만 보니 짝수는 마지막에 순간이동으로 들어간다. 

즉 n/2 까지의 최단거리만 구해주면 마지막에 순간이동으로 들어가면 된다. 

예를 들어 n= 10인경우    10/2 = 5 까지의 최단거리를 구해주면 쉽다.  

따라서 5까지의 최단거리는 2   그리고 마지막에 순간이동으로 도착

결국 n= 10일때의 최단거리는 2이다.

그렇다면 짝수는  2로 계속 나누어주면 된다. 

언제까지 ? 홀수가 될때까지  

그럼 홀수일때는 어떻게 할까? 

홀수는 마지막에 무조건 점프로 도착해야한다.  

이동하는 거리에 도착하는 건전지 사용량의 최솟값을 구해야 하기에 

순간이동으로 거리가 초과하면 안된다. 따라서 순간이동을 사용하면 무조건 짝수 거리가 나오기에 마지막에 무조건 점프를 써줘야한다.

그렇다면 순간이동하고 마지막 점프하기전 까지의 최단거리의 건전지 사용량을 구하고  + 1을 해주면된다.

 

n = 5 일때  마지막은 무조건 점프를 써줘야하니 

n -1  = 4 까지의 최단거리 일때 건전지 최소 사용량을 구해주면 된다. 

4까지의 result는 1이라고 일전에 구했으니 1 에다가 아까 -1 해준 1을 다시 더 해주면 2가 된다.  이게 result이다. 

 

결국 이 문제는 간단하다 . 짝수이면 2로계속 나눠준다 언제까지 ?  n = 1이 되거나 홀수가 될때까지 

홀수가 될때는 result를  + 1 해주고  n = n-1을 해주고 다시 n = 1이 되거나 홀수가 될때까지 나눠준다. 

이렇게해서 n = 1 이되면 그때 result를 return 해주면 된다. 

 

 

---

다른 사람 풀이 

 

const solution = (n) => n.toString(2).match(/1/g).length;

이렇게 2진법으로 변환한뒤에  1의 개수로 문제를 푼 사람도 있다. 

 

실제로 확인해봤는데 1의 개수와 정답이 동일하다. 

왜이렇게 되는지는 아직 모르겠다. 

 

n = 3 일때

 2진법은  11

 

n  = 4 일때 

  2진법은 100

 

n = 5 일때

  2진법은 101

 

n = 6 일때 

   2진법은 110

 

n = 7 일때는

   2진법은 111

 

n = 8 일때는

  2진법은 1000

 

n = 9 일때는

  2진법은 1001

 

1일때가 점프고 0일때가 순간이동 같은데 완벽하게 매치되지는 않는다. 

하지만 1의 개수와 result는 똑같다. 

1과 1사이의 순간이동은 생략되는 것 같다.