[프로그래머스] Lv3 카운트 다운

문제 풀이 방법 

문제에선 구하라고 하는 값은 최선의 경우 던질 다트 수(최솟값)와 그 때의 싱글 또는 불을 맞춘 횟수(합)을 순서대로 배열에 담으라고 합니다. 다트를 던지는 방법은 싱글, 2배, 3배, 불 이렇게 4가지의 방법이 있고 최솟값을 구하라는 문제에서 백트래킹 + DP 알고리즘을 생각했습니다. 백트래킹 + DP 알고리즘은 몇몇 테스트는 통과를 했지만, 런타임 예외가 발생했습니다. 

 

 

문제에서 target이 100,000이기도 하고 DFS를 사용한 경우 한 depth가 늘어날때마다 4개의 경우로 분기가 되기 때문에 재귀 호출이 매우 깊어집니다. 백트래킹을 적용할 시 이미 방문한 상태보다 더 나은 경우만 탐색해야 하지만, 싱글/볼을 최대로 하는 조건까지 고려하는 경우엔 백트래킹을 적용한다고 해도 경우의 수가 너무 많아져서 효율적인 가지치기가 어렵습니다.

 

그럼 어떻게 접근을 해야할까요?

 

문제에서 다트의 최소 횟수를 찾아야 하므로, 최단 경로 탐색에 적합한 BFS를 사용하여 접근합니다. 제일 다트의 갯수가 적을때부터 한 계층 단위로 탐색을 하기 때문에 더 빠른 시간에 값을 찾을 수 있게 됩니다.

 

방문 조건은 다음과 같습니다.

• 해당 점수를 처음 방문하는 경우
• 이미 방문했지만, 현재 경로에서 사용한 다트 개수가 더 적은 경우
• 다트 개수는 동일하지만, 싱글 또는 볼을 맞춘 횟수가 더 많은 경우

이 조건을 만족하는 경우에, 해당 상태값을 Queue에 추가해 탐색을 진행합니다.

 

상태값은 [현재 점수, 사용한 다트 개수, 불과 싱글의 합 개수]로 지정을 해주었고,

방문 처리시 확인하는 상태 값은 [사용한 다트 갯수, 불과 싱글의 합 개수]로 지정해주었습니다.

 

방문처리를 하는 배열은 int형으로 사용할 경우, 점수의 범위가 너무 커져 메모리 낭비가 발생할 수 있습니다.

문제에서 target의 최댓값은 100,000이기 때문에 점수 상태를 배열로 관리하는 경우 배열의 크기가 커집니다.

 

그렇기 때문에, 배열로 관리하는 것보다는 HashMap을 사용해서 관리합니다.

그 이유는 HashMap에는 실제로 방문하는 점수만 저장을 하기 때문입니다.  또한 key, value 형식이기 때문에 O(1)의 시간복잡도로 바로 조회가 가능합니다.

 

 

풀이 코드

import java.util.*;

class Solution {
    public int[] solution(int target) {
        int[] answer = {};
        
        Queue<int[]> queue = new LinkedList<>();
        Map<Integer, int[]> visited = new HashMap<>();
        
        queue.offer(new int[]{target, 0, 0});
        visited.put(target, new int[]{0,0});
        
        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            int curPoint = cur[0];
            int dartCnt = cur[1];
            int singleBoolCnt = cur[2];
            
            if(curPoint == 0) {
                answer = new int[]{dartCnt, singleBoolCnt};
            }
            
            for(int i = 1; i <= 20; i++) {
                check(queue,visited,curPoint-i, dartCnt + 1, singleBoolCnt + 1);
                check(queue,visited,curPoint-2*i, dartCnt + 1, singleBoolCnt);
                check(queue,visited,curPoint-3*i, dartCnt + 1, singleBoolCnt);
            }
            
            check(queue, visited, curPoint-50, dartCnt + 1, singleBoolCnt + 1);
        } 
        
        return answer;
    }
    
    private void check(Queue<int[]> queue, Map<Integer, int[]> visited, int newPoint, int newDartCart, int newSingleBoolCnt) {
        if(newPoint < 0) {
            return;
        }
        
        if(!visited.containsKey(newPoint) || 
           visited.get(newPoint)[0] > newDartCart || 
           (visited.get(newPoint)[0] == newDartCart && visited.get(newPoint)[1] < newSingleBoolCnt)) {
            visited.put(newPoint, new int[]{newDartCart, newSingleBoolCnt});
            queue.offer(new int[]{newPoint, newDartCart, newSingleBoolCnt});
        }
    }
 }


ㄴ

 

 

 

시간 복잡도

점수의 갯수 : 20개 ( 1부터 20점)

싱글, 더블, 트리플 : 3개

불리언 : 1개

 

각 상태에서 가능한 모든 경우는 61가지가 존재합니다.

Queue에 추가되는 원소의 갯수를 n으로 잡게되면 최종적으로 O(61n)이되고, 이는 O(n)이 됩니다.

 

출력 결과

 

짚고 넘어갈 포인트

• 범위가 큼에도 불구하고 단순 백트래킹 + DP로만 생각했고, 가지치기를 하면 어느정도 큰 범위가 커버될 것이라는 안일한 생각
• 너무 큰 범위를 가져서 방문 배열에 값을 전부 담을 수 없는 경우엔 다른 방식을 생각(최소인 경우엔 BFS + 방문 조건)
• HashMap을 사용한 방문 처리