[프로그래머스] Lv.2 : 점프와 순간이동 - 자바[Java]

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

프로그래머스

 

풀이 - BFS (실패)

처음에 문제를 보고 BFS로 풀려고 했다. 하지만 N이 10억 이하의 자연수이며 풀이 과정도 시간이 오래 걸리는 문제가 생겼다. 정확성 테스트는 모두 맞았지만, 효율성 테스트에서 메모리 초과/시간 초과로 모두 실패했다. 다음은 BFS를 사용한 테스트에서 실패한 코드다.

import java.util.*;

public class Solution {
    public int solution(int n) {
        
        int[] powers = new int[n+1];
        getPower(powers, n);

        return powers[n];
    }
    
    private static void getPower(int[] powers, int n) {
        for (int i = 1; i <= n; i++)
            powers[i] = i;
        
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{1, 1});
        
        while(!q.isEmpty()) {
            int[] cur = q.poll();
            int pos = cur[0];
            int power = cur[1];
            
            for (int nextPos = pos * 2; nextPos <= n; nextPos *= 2) {
                if (powers[nextPos] > power) {
                    powers[nextPos] = power;
                    q.add(new int[]{nextPos, power});
                }
            }
            
            for (int nextPos = pos + 1; nextPos <= n; nextPos++) {
                if (powers[nextPos] > power+(nextPos-pos)) {
                    powers[nextPos] = power + (nextPos-pos);
                    q.add(new int[]{nextPos, powers[nextPos]});
                }
            }
        }
        
    }
}

• powers[i] = i번째 칸에 도착하기 위한 배터리 최소 사용량
• BFS를 수행할 때 큐에 (칸 위치, 최소 배터리 사용량)을 저장하여 큐에서 꺼낼 때 마다 powers 값을 업데이트하고 큐에 값을 집어넣는다.
• 하지만 이렇게 하면 똑같은 nextPos가 큐에 여러 개가 들어갈 수 있으며, 불필요하게 powers 값을 업데이트 해야 하는 경우가 생긴다.

 

위의 코드를 수정하여 다시 풀어보았지만 여전히 효율성 테스트에서 실패했다.

import java.util.*;

public class Solution {
    public int solution(int n) {
        
        int[] powers = new int[n+1];
        getPower(powers, n);

        return powers[n];
    }
    
    private static void getPower(int[] powers, int n) {
        for (int i = 1; i <= n; i++)
            powers[i] = i;
        
        Queue<Integer> q = new LinkedList<>();
        q.add(1);
        
        while(!q.isEmpty()) {
            int pos = q.poll();
            
            for (int nextPos = pos * 2; nextPos <= n; nextPos *= 2) {
                if (powers[nextPos] > powers[pos]) {
                    q.remove(nextPos);
                    powers[nextPos] = powers[pos];
                    q.add(nextPos);
                }
            }
            
            for (int nextPos = pos + 1; nextPos <= n; nextPos++) {
                if (powers[nextPos] > powers[pos]+(nextPos-pos)) {
                    q.remove(nextPos);
                    powers[nextPos] = powers[pos] + (nextPos-pos);
                    q.add(nextPos);
                }
            }
        }
        
    }
}

• BFS를 수행할 때 큐에 칸 위치만 저장하여, powers 값을 업데이트할 때 nextPos가 이미 큐에 있으면 그 값을 제거하고 다시 큐에 집어넣는다.

 

---

풀이

위의 풀이는 0에서 시작하여 도착점에 도착하도록 로직을 짰다.

하지만 도착점에서 0으로 되돌아온다고 생각하면 매우 쉽게 문제를 풀 수 있다.

로직

1. 정답을 저장할 ans를 선언하고 0으로 초기화한다.

2. n이 0이 될 때까지 while문을 통해 다음을 반복한다.

• n이 짝수면 n을 2로 나눈 값을 n에 저장한다.
• n이 홀수면 n에서 1을 뺀 값을 n에 저장하고 ans에 1을 더한다.

3. ans를 리턴한다.

 

코드

import java.util.*;

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

        return ans;
    }
}

 

 

⭐시작점 -> 도착점으로 풀었는데 안되면 도착점 -> 시작점으로 되돌아오는 것도 생각해보자