[Javascript] 프로그래머스 - 점프와 순간 이동

문제 설명

OO 연구소의 아이언 슈트는 다음과 같은 두 가지 이동 방식을 지원합니다:

1. K 칸 점프: 건전지를 K만큼 사용합니다.
2. 순간 이동: 현재 위치의 거리 x 2에 해당하는 위치로 이동하며, 건전지 사용량은 소모되지 않습니다.

구매자는 특정 거리 N만큼 떨어져 있는 목적지로 이동하려고 하며, 건전지 사용량을 최소화해야 합니다.

이때 건전지 사용량의 최솟값을 구하는 함수를 작성하세요.

---

제한 조건

1. N: 1 이상 10억 이하의 자연수
2. K: 1 이상의 자연수

---

해결 방법

알고리즘: 비트마스킹 (Bit Manipulation)

1. 문제의 본질
   • 순간 이동은 건전지를 소모하지 않으므로 최대한 많이 사용해야 합니다.
   • 점프는 1칸씩 수행하며 건전지를 소모합니다.
2. 효율적 접근
   • N을 이진법으로 표현했을 때, 1의 개수가 최소 점프 횟수와 동일합니다.
     • 순간 이동은 위치를 두 배로 이동하는 것이므로, 이진법에서 왼쪽으로 쉬프트하는 효과가 있습니다.
     • 점프는 이진법에서 1을 처리해야 하는 경우와 동일합니다.
3. 구현 방법
   • N을 이진법으로 변환하고 1의 개수를 카운트합니다.
   • 이는 최소 건전지 사용량과 같습니다.

---

시간 복잡도

1. 이진법 변환 및 1의 개수 계산
   • 숫자 N을 이진법으로 변환하는 데 O(log N) 시간이 소요됩니다.
   • 변환된 이진법 문자열에서 1의 개수를 세는 데 O(log N)입니다.
2. 총 시간 복잡도
   • O(log N)

---

구현 코드

function solution(n) {
  return n.toString(2).split("1").length - 1;
}