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

제출한 코드

1차 제출한 코드 - 정확성 60.0 효율성 0 ( 시간 초과 + 메모리 초과 )

import java.util.*;

public class Solution {
    
    public int solution(int n) {
        
        int cost = n;
        
        // 방문 처리용 배열 세팅
        int[] v = new int[n+1];
        Arrays.fill(v, Integer.MAX_VALUE);
        
        Deque <int[]> q = new ArrayDeque<>();
        
        q.add(new int[] {0,0});
        
        while(!q.isEmpty()){
            int[] cur = q.poll();         
            
            // 불필요한 연산 제거
            if(v[cur[0]] <= cur[1] || cost <= cur[1]){
                continue;
            }
            // 방문처리
            else{
                v[cur[0]] = cur[1];
            }
            
            // 도착한 경우
            if(cur[0] == n){
                cost = cur[1];
                continue;
            }
            
            // 순간이동 하는 경우
            if(cur[0] * 2 <= n){
                q.add(new int [] {cur[0] * 2, cur[1]});
            }
            
            // 점프하는 경우
            if(v[cur[0]+1] > cur[1] + 1){
                q.add(new int [] {cur[0] + 1, cur[1] + 1 });
            }
            
        }
        
        return cost;
    }
}

 

처음 생각한 로직

1. 단순 BFS 문제일꺼라고 생각했다.

2. 순간이동은 *2 점프하는 경우는 K만큼이니 +1로 고정시켜서 연산 진행

3. 중복된 연산을 피하기 위한 방문처리

 

틀린 이유 추측

1. 불필요한 연산으로 인한 메모리 및 시간 초과 발생

 

의문점

1. 시간 제한이 얼마인가?

2. 메모리 제한이 얼마인가?

---

 

 

2차 제출한 코드 - 정확성 60.0 , 효율성 40.0 

 

import java.util.*;

public class Solution {
    
    public int solution(int n) {
        
        int cost = 0;
        
        while(n!=0){
        
        	// 2로 나누었을 때 나머지가 0 이면 나누기 2
            if(n%2 == 0){
                n = n/2;
            }
            
            // 아닌 경우 1 감소
            else{
                n-=1;
                cost++;
            }
        }
        
        return cost;
    }
}

 

생각한 로직

1. 입력받은 정수 n을 나누어지는 경우 2로 나눈다.

2. 2로 나눠지지 않는 경우 1을 감소 시키면서 비용을 증가한다.

3. 위 과정으로 n이 0이 될 때 까지 반복한다.