[Programmers / Level 2] 12980. 점프와 순간 이동 (Java)

💡 Info

• 난이도: Lv2
  프로그래머스 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12980
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/2/점프와 순간 이동

입출력 조건

입출력 예시

문제 이해

• 거리 N만큼 떨어진 장소로 이동하는 문제(건전지 사용량 최소화가 중점)
• 이동 방법
  • 점프 : K칸 점프 -> K만큼의 건전지 사용량 발생
  • 순간 이동 : 현재까지 온 거리x2에 해당하는 위치로 이동(건전지 사용량 없음)

알고리즘

풀이 시간 : 12분

• N -> 0 순서대로 역순 이동하는 방식 활용
• 짝수, 홀수 나눠서 처리(반복)
  • N이 짝수면 -> 2로 나눠서 순간 이동
  • N이 홀수면 -> -1하고 순간 이동(건전지 사용량 +)

import java.util.*;

public class Solution {
    public int solution(int n) {
        int answer = 0;
        
        while (n > 0) {
            if (n % 2 == 0) {
                n /= 2;
            } else {
                n--;
                answer++;
            }
        }
        
        return answer;
    }
}

결과

✍️ 다른 풀이 - 이진법

• N을 이진법으로 변환해서 코드를 최적화 -> 1의 개수를 세면 됨.
• 시간 복잡도는 O(logN)으로 기존 방식과 동일하나, 코드 줄을 많이 줄일 수 있다는 점에서 좋은 코드라고 생각.

import java.util.*;

public class Solution {
    public int solution(int n) {
        return Integer.toBinaryString(n).replace("0", "").length();
    }
}