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

1. Input

1) int 변수 n

2) n은 아이언 슈트 구매자가 이동하려는 거리

 

2. Output

1) 사용해야 하는 건전지의 최솟값을 담은 int 변수

2) 한 번에 k칸 앞으로 점프하면 건전지를 k만큼 사용한다.

3) (현재까지 온 거리 * 2)에 해당하는 위치로 순간이동 할 때는 건전지가 소모되지 않는다.

 

3. Constraint

1) n: 1 이상 10억 이하의 자연수

2) k: 1 이상의 자연수

 

4. Example

Input: n=5 -> Output: 2

설명: 거리가 5만큼 떨어진 곳으로 갈 때

1) 처음 위치 0에서 5칸을 앞으로 점프하면 바로 도착하지만, 건전지 사용량이 5만큼 든다.

2) 처음 위치 0에서 2칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리: 2)*2에 해당하는 위치로 이동할 수 있으므로 위치 4로 이동한다. 이때 1칸을 앞으로 점프하면 도착하므로 건전지 사용량이 3만큼 든다.

3) 처음 위치 0에서 1칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리: 1)*2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동된다. 이때 다시 순간이동 하면 (현재까지 온 거리: 2)*2 만큼 이동할 수 있으므로 위치 4로 이동한다. 이때 1칸을 앞으로 점프하면 도착하므로 건전지 사용량이 2만큼 든다.

- 위의 경우 3번째 경우가 건전지 사용량이 가장 적으므로 2를 반환한다.

 

5. Code

1) 첫 코드(2022/12/02)

int ans = 0;
while(n>0){
    ans += n%2;
    n /= 2;
}
return ans;

2) 1번이 맞는 것을 확인한 후 다시 짜본 코드(2022/12/02)

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

  - 1번보다 훨씬 간결해졌지만, 아주 약간 느리고 공간도 아주 약간 더 사용한다.