[프로그래머스] 숫자 변환하기, java

- 문제

프로그래머스

- 풀이

 

최초 DFS를 이용해 접근해보려하다, 시간초과로 인해 풀이에 실패하였습니다. 한 번 방문했던 곳에 다시 방문하지 않는다 라는 아이디어도 쉽게 적용이 되지 않아서 구글링을 진행했고, DP를 이용한 풀이를 이해하고 풀어보았습니다.

 

1. DP를 이용한 풀이

class Solution {
    
    public int solution(int x, int y, int n) {
        int answer = 0;
        
        //각 숫자들에 도달하는데 필요한 연산 횟수를 담을 dp 배열입니다.
        int[] dp = new int[y+1];
        
        //우리가 필요한 숫자는 x~y까지의 수 입니다.
        //x-y까지의 수들을 확인할 수 있는 for문을 시작합니다.
        for(int i=x; i<=y; i++){
            
            //x의 경우 도달하는데 0번의 연산이 필요하니 건너뛰어주고,
            //i가 x보다 큰 모든 경우 현재 dp[i]가 0이라는 의미는 n을 더하거나, *2, *3연산을 하더라도
            //해당 수에 도달할 수 없다는 의미입니다. 따라서 해당 수에는 -1을 담아줍니다.
            if(i!=x && dp[i] == 0){
                dp[i] = -1;
                
            //dp[i]가 0이 아니라면 해당 위치에서 다음 연산을 진행합니다.
            } else {
                
                //현재 수에서 n을 더하더라도 y보다 크지 않다면, 다음 연산을 할 의미가 있습니다.
                if(i+n<=y){
                    
                    //dp[i+n]에 처음 도달하는 경우 현재의 연산횟수가 최소값이므로
                    //현재 수인 i까지 도달하는데 걸린 연산횟수 dp[i]에 연산횟수 1을 더한 수를 입력해줍니다.
                    
                    //만약 이미 dp[i+n]에 도달한 적이 있다면 dp[i+n]는 0이 아닐 것 입니다.
                    //따라서 Math.min()함수를 통해 이번 연산에 dp[i+n]에 도달하는 횟수인 dp[i]+1와 
                    //이전에 i+n 수에 도달하는데 걸렸던 횟수 dp[i+n] 
                    //둘 중 더 작은 횟수를 dp[i+n]를 입력해줍니다.
                    
                    //이렇게 함으로서 같은 수에 여러번 도달한다고 하더라도, 가장 최소 횟수로 해당 위치에 도달한 횟수를 구할 수 있습니다.
                    dp[i+n] = (dp[i+n] == 0) ? dp[i]+1 : Math.min(dp[i+n], dp[i]+1);
                }
                //i+n에 했던 동작과 같이 연산만 i*2로 바꾸어 진행해줍니다.
                if(i*2<=y){
                    dp[i*2] = (dp[i*2] == 0) ? dp[i]+1 : Math.min(dp[i*2], dp[i]+1);   
                }
                //i+n에 했던 동작과 같이 연산만 i*3으로 바꾸어 진행해줍니다.
                if(i*3<=y){
                    dp[i*3] = (dp[i*3] == 0) ? dp[i]+1 : Math.min(dp[i*3], dp[i]+1); 
                }
                
            }
        }
        
        //이제 완성된 각 수의 도달 횟수 dp배열에서 y에 도달하는 횟수를 반환해줍니다.
        return dp[y];
    }
}

 

소요 시간은 다음과 같이 확인되었습니다.

DP를 이용한 풀이

2. BFS를 이용한 풀이

DP를 이용한 풀이를 적용해 본 이후 DFS가 아니라 BFS였다면 해결이 가능할 것 같아, BFS와 방문처리를 이용한 풀이를 만들어 보았습니다.

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        int answer = -1;
        HashSet<Integer> set = new HashSet<>();
        Queue<Integer> q = new LinkedList<>();
        q.add(x);
        set.add(x);
        
        int idx = 0;
        run : while(!q.isEmpty()){
            int size = q.size();
            for(int i=0; i<size; i++){
                int now = q.poll();
                if(now == y){
                    answer = idx;
                    break run;
                } else {
                    if(now+n<=y && !set.contains(now+n)){
                        set.add(now+n);
                        q.add(now+n);
                    }
                    if(now*2<=y && !set.contains(now*2)){
                        set.add(now*2);
                        q.add(now*2);
                    }
                    if(now*3<=y && !set.contains(now*3)){
                        set.add(now*3);
                        q.add(now*3);
                    }
                }
            }
            
            idx++;
        }
        
        return answer;
    }
}

 

해당 풀이 또한 성공적으로 문제를 해결할 수 있었습니다.

BFS, HashSet을 이용한 풀이

 

다만 DP를 이용한 풀이와는 확연하게 다른 소요시간을 보여주었습니다. 그리고 저는 방문처리를 HashSet 자료구조의 contains()를 이용하여 진행을 하였는데, 더 단순한 방법인 boolean[]을 이용하면 차이가 발생할까? 라는 궁금증이 생겼습니다. 사실 Set의 contains()와 boolean[]의 index 접근 둘 다 시간복잡도가 O(1)으로 알고 있었기 때문에 더욱 궁금했습니다. 그래서 다음과 같이 진행해 보았습니다.

 

2-1 boolean[]을 이용한 방문처리 풀이

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        
        //연산 횟수를 담을 int 변수입니다.
        //어떤 연산으로도 y에 도달할 수 없다면 -1을 반환해야 하기 때문에
        //최초 값을 -1으로 할당합니다.
        int answer = -1;
        
        //방문 처리를 할 boolean 배열입니다.
        //bfs를 이용하여 연산을 할 경우에는 특정한 수에 도달하는 순간이 항상 최소 연산 횟수입니다.
        //따라서 한번 만났던 숫자는 다시 만날 필요가 없기 때문에 방문 처리를 통해 연산 시간을 줄여줍니다.
        boolean[] visited = new boolean[y+1];
        
        //bfs를 하기 위해 Queue 자료구조를 사용합니다.
        Queue<Integer> q = new LinkedList<>();
        
        //시작 수인 x를 Queue에 넣어줍니다.
        //그리고 x에 이미 방문했음을 표시해줍니다.
        q.add(x);
        visited[x] = true;
        
        //몇 번의 연산을 통해 해당 수에 도달하게 되었는지 표시해 줄 idx입니다.
        int idx = 0;
        
        //dfs연산을 진행합니다.
        //q에서 꺼낸 수가 y값과 같다면 더 이상 탐색을 할 필요가 없기 때문에
        //바로 탐색을 종료시켜 주기 위해 while문에 run이라는 이름을 할당해 주었습니다.
        run : while(!q.isEmpty()){
            
            //현재 Queue 원소의 갯수를 세어줍니다.
            //동일한 연산 횟수를 통해 도달하는 수들을 파악하기 위해, 사용합니다.
            int size = q.size();
            
            //이번 size만큼의 수는 idx번의 연산만에 도달한 수들 입니다.
            for(int i=0; i<size; i++){
                
                //q에서 수를 꺼내줍니다.
                int now = q.poll();
                
                //꺼낸 수가 y와 같다면,
                if(now == y){
                    answer = idx;   //answer에 현재까지의 연산 횟수를 담아주고,
                    break run;      //반복을 종료해줍니다.
                
                //꺼낸 수가 y보다 작은 경우입니다.
                } else {
                    
                    //이제 사용할 수 있는 연산들을 진행합니다.
                    //이번 연산 now+n이 y이하이고, 아직 방문한 적이 없는 수라면,
                    if(now+n<=y && !visited[now+n]){
                        visited[now+n] = true;  //방문 처리를 해주고
                        q.add(now+n);           //q에 추가하여 다음 연산을 진행해보도록 합니다.
                    }
                    
                    //now*2 연산 또한 위와 같은 과정을 진행합니다.
                    if(now*2<=y && !visited[now*2]){
                        visited[now*2] = true;
                        q.add(now*2);
                    }
                    
                    //now*3 연산 또한 위와 같은 과정을 진행합니다.
                    if(now*3<=y && !visited[now*3]){
                        visited[now*3] = true;
                        q.add(now*3);
                    }
                }
            }
            
            //위 for문이 지나도록 y값이 나오지 않았다면
            //한번 더 연산을 해봐야 하므로 idx값을 증가시켜줍니다.
            idx++;
        }
        
        //bfs를 통해 확인한 연산 횟수를 반환합니다.
        return answer;
    }
}

 

이 두번째 풀이는 코드를 보시면 아시겠지만, 정확히 방문처리의 방식만 바꾼 것을 확인할 수 있습니다. 그리고 소요시간의 차이는 선명하게 드러났습니다.

BFS, boolean[]를 이용한 풀이

 

물론 DP를 이용한 풀이에는 미치지 못하지만, 확실하게 HashSet을 이용한 방문처리보다 빠른 성능을 보여주었습니다. 그리고 이에 대한 궁금증은 다음 게시글에서 알아보도록 하겠습니다.