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

1. 문제

---

프로그래머스

2. 풀이 과정

---

1. 배터리를 사용하지 않고 현재위치* 2의 위치로 순간 이동

2. 배터리를 K만큼 소모하고 K칸만큼 이동

이 두 가지 기능이 있는 슈트을 가지고 N만큼 이동한다고 했을 때, 배터리 소모량의 최솟값을 구하는 문제이다.

 

일단 배터리를 소모하면 안 좋기 때문에 최대한 1번 방식으로 이동하는 것이 좋다. 

따라서 1번방식으로 현재위치에서 될 수 있으면 곱하기 2를 하고 어쩔 수 없는 경우엔 2번방식으로 배터리를 1소모하고 1만큼 움직여서 N을 만들어야 한다.

하지만 앞으로 이동하는 입장에선 그 어쩔 수 없이 배터리를 소모해야하는 경우를 파악하기 힘들다. 그러므로 거꾸로 움직여야한다.

그 전략은 다음과 같다.

N에서부터 거꾸로 이동하되

1. 현재위치가 짝수면 이전에 순간이동으로 올 수 있었다는 말이므로 나누기 2

2. 현재위치가 홀수면 이전에 순간이동으로는 못온다는 말이므로 빼기 1(이 경우 배터리 소모1)

 

이를 반복해서 현재 위치를 0으로 만들면 된다.

 

 

3. 내 코드

---

import java.util.*;

public class Solution {
    public int solution(int n) {

        int cnt = 0;
        while(n > 0) {
        	// 현재 위치가 홀수면 1빼고 1소모
            if(n % 2 != 0){
                n--;
                cnt++;
            }
            
            // 현재 위치가 짝수면 나누기 2
            n /= 2;
        }
        return cnt;
    }
}

시간 복잡도

• O(logN)

 

생각해볼 점

저 코드 과정을 자세히 보니 10진수를 2진수로 변환하는 과정과 비슷하다.

해당 문제는 나머지가 1일 때 카운트를 셌다. 그러므로 n을 2진수로 변환하고 변환한 2진수의 1의 갯수를 세면 답이 된다.

return Integer.toBinaryString(n).replace("0", "").length();