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

점프와 순간 이동

문제링크

풀이

그리디로 단순 구현하여 푸는 문제

첫번째 풀이를 통해 정확성 테스트는 통과하였지만, 효율성 테스트를 통과하지 못하였다.
백준의 숨바꼭질을 이런 형식으로 풀었었는데 해당 문제보다 간단하여 그리디로 바로 구현할 수 있었다.

방문 여부를 확인하는 배열, 몇번만에 해당 장소에 도착했는지를 확인하는 times 배열을 만들었고
queue를 활용하여 횟수마다 2배 이동 혹은 1칸씩 이동하여 N예 도착시 times에 저장된 N위치의 값을 가져오는 풀이이다.

두번째 풀이는 간단하게 n에서 0의 위치로 온다고 판단하여 2의 배수이면 나누기 2를 아니라면 -1을 하여 계산하여 구현하였다.

코드

첫번째 풀이 (실패)

import java.util.*;

// k칸 앞으로 or (현재까지 온거리) * 2 위치로 순간이동
public class Solution {
    
    public static boolean[] visited;
    public static int[] times;
    
    public static int N;
    
    public int solution(int n) {
        int ans = 0;
        N = n;

        visited = new boolean[n + 1]; // 방문 여부
        times = new int[n + 1]; // 횟수
        
        bfs(0);

        return times[N];
    }
    
    public static void bfs(int start) {
        Queue<Integer> queue = new ArrayDeque<>();
        
        visited[start] = true;
        queue.offer(start);
        while(!queue.isEmpty()) {
            int k = queue.poll();
            if (k == N) return;
            
            if (k * 2 <= N && !visited[k * 2]) {
                visited[k * 2] = true;
                times[k * 2] = times[k];
                queue.offer(k * 2);
            }
            if (k + 1 <= N && !visited[k + 1]) {
                visited[k + 1] = true;
                times[k + 1] = times[k] + 1;
                queue.offer(k + 1);
            }
        }
        
    }
}

두번째 풀이

import java.util.*;

// k칸 앞으로 or (현재까지 온거리) * 2 위치로 순간이동
public class Solution {
    
    public int solution(int n) {
        
        int answer = 0;
        
        while (n != 0) {
            if (n % 2 == 0) {
                n /= 2;
            } else {
                n -= 1;
                answer++;
            }
        }

        return answer;
    }
}