프로그래머스 점프와 순간 이동 (JAVA)

https://programmers.co.kr/learn/courses/30/lessons/12980

코딩테스트 연습 - 점프와 순간 이동

 

저는 수식으로 문제를 해결하였습니다.

처음에는 bfs를 이용해 문제를 해결하려 하였지만, 시간초과를 피할 수 없어 다른 방법을 생각하였습니다.

2를 나누면서 나누어떨어지지 않으면 result를 하나 늘려주고 마지막으로 result를 리턴하여 문제를 해결하였습니다.

 

import java.util.*;

public class Solution {
    public int solution(int n) {
        int ans = divide(n);
        return ans;
    }
    private int divide(int n){
        int result = 0;
        while(n > 0){
            if(n % 2 != 0){
                result++;
            }
            n /= 2;
        }
        return result;
    }
    private int bfs(int target){
        Map<Integer,Integer> visited = new HashMap<>();
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->{
            return o1[1] - o2[1];
        });
        pq.offer(new int[] {0,0});
        visited.put(0,0);
        while(!pq.isEmpty()){
            int[] now = pq.poll();
            if(now[0] == target){
                return now[1];
            }
            int next = 2 * now[0];
            int time = now[1];
            if(next > 0 && (!visited.containsKey(next) || visited.get(next) > time) ){
                visited.put(next,time);
                pq.offer(new int[] {next,time});
            }
            next = now[0]+1;
            time = now[1]+1;
            if(next > 0 && (!visited.containsKey(next) || visited.get(next) > time) ){
                visited.put(next,time);
                pq.offer(new int[] {next,time});
            }
        }
        return -1;
    }
}