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

풀이 날짜 : 2025.04.30
문제 유형 : Summer/Winter Coding(~2018)
문제 제목 : 점프와 순간 이동
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12980

Intuition

• 주어진 n만큼 이동하는 데 필요한 최소한의 점프 횟수를 구하는 문제이다.
  • 순간이동은 현재까지의 이동거리 * 2 의 위치로 이동하고 건전지를 사용하지 않는다.
  • 점프는 이동하는만큼의 건전지를 사용한다.
• 그리디 알고리즘 : 항상 선택 가능한 최선의 방법을 선택한다.
  • 순간이동을 최대한 많이 쓰고, 순간이동을 할 수 없을 때만 점프를 해야 한다.
  • 6의 경우, [ 점프(0 + 1 = 1) → 순간이동(1 * 2 = 2) → 점프(2 + 1 = 3) → 순간이동(3 * 2 = 6) ] ⇒ 최소 2번의 점프가 필요하다.
  • 6에서 0까지 역으로 생각해보면 순간이동을 할 수 있는 칸은 짝수 번째 칸이고, 순간이동을 할 수 없는 칸은 홀수 번째 칸이다.
• 비트 조작 : 규칙이 2의 배수, 짝/홀과 관련 있음
  • 6을 이진수로 변환하면 1010이고, [ 점프 → 순간이동 → 점프 → 순간이동 ] ⇒ 최소 2번의 점프가 필요하다.
  • n을 이진수로 바꾸면 1이 있는 자리마다 점프하는 것과 같다.

Approach

• 건전지의 사용량을 저장할 변수(used)를 선언한다. 이 값은 점프 횟수와 같다.
• n이 0이 될 때까지 반복한다.
  • n이 짝수면 n을 2로 나눈다. (순간이동, 건전지 사용 없음)
  • n이 홀수면 n에서 1을 빼고, used를 1 늘린다. (점프, 점프한 만큼 건전지 사용)
• used를 반환한다.

Complexity

• Time complexity : O(log n)
  • 이동해야 하는 거리를 n이라고 할 때 계속 2로 나눠지므로 O(log n)이다.
• Splace complexity : O(1)
  • 배열이나 객체 등의 추가적인 저장 공간은 없다.

Code (JS)

• 그리디 알고리즘

function solution(n) {
    let used = 0;

    while (n !== 0) {
        if (n % 2 === 0) {
            n /= 2;
        } else {
            n -= 1;
            used += 1;
        }
    }

    return used;
}

• 비트 조작

function solution(n) {
    let used = 0;
    while (n > 0) {
        used += n & 1;  // 마지막 비트가 1이면(=홀수면) 점프가 필요
        n >>= 1;        // n을 오른쪽으로 1비트 이동 = n / 2
    }
    return used;
}