[Programmers] 광물 캐기 / ⭕

프로그래머스

 

1. 제출 코드 (1시간 16분 45초 / 백트래킹)

import java.util.*;

class Solution {
    static ArrayList<String> tools = new ArrayList<>();
    static boolean[] visited;
    static int tool_cnt;
    static int answer = Integer.MAX_VALUE;
    public int solution(int[] picks, String[] minerals) {
    	// 곡괭이 수 COUNT
        for(int num : picks) {
            tool_cnt += num;
        }
        // 추후, 피로도를 계산하기 위해 곡괭이 저장
        for(int i = 0; i < picks.length; i++) {
            for(int j = 0; j < picks[i]; j++) {
                if(i == 0) {
                    tools.add("diamond");
                } else if (i == 1) {
                    tools.add("iron");
                } else {
                    tools.add("stone");
                }
            }
        }
        // 곡괭이 사용 여부 (방문 체크 배열)
        visited = new boolean[tool_cnt];
        backtracking(0, 0, 0, minerals);
        return answer;
    }
    
    static public void backtracking(int depth, int score, int idx, String[] minerals) {
    	// score >= answer이면 이후에는 고려할 필요가 없음
        if(score >= answer) return;
        // 광물을 끝까지 캐거나 곡괭이를 다 사용했을 경우
        if(idx == minerals.length || depth == tool_cnt) {
            answer = Math.min(answer, score);
            return;
        }

        for(int i = 0; i < tool_cnt; i++) {
        	// 곡괭이 사용 안 했을 때
            if(!visited[i]) {
            	// 피로도 계산
                int temp = 0;
                // 광물을 연속으로 캘 수 있는 개수
                int len = 0;
                visited[i] = true;
                
                if(idx + 5 >= minerals.length) {
                    len = minerals.length;
                } else {
                    len = idx + 5;
                }
                // 현재 곡괭이로 연속 5개 광물 피로도 계산
                for(int j=idx; j < len; j++) {
                    if(tools.get(i).equals("diamond")) {
                        temp += 1;
                    } else if(tools.get(i).equals("iron")) {
                        if(minerals[j].equals("diamond")) {
                            temp += 5;
                        } else {
                            temp += 1;
                        }
                    } else {
                        if(minerals[j].equals("diamond")) {
                            temp += 25;
                        } else if(minerals[j].equals("iron")) {
                            temp += 5;
                        } else {
                            temp += 1;
                        }
                    }
                }
                // 다음 곡괭이 사용
                backtracking(depth + 1, score + temp, len, minerals);
                // 어떤 곡괭이를 먼저 사용했는지 모르니까 전부 탐색
                visited[i] = false;
            }
        }
    }
    
}

 

2. 실패 코드

import java.util.*;

class Solution {
    static ArrayList<String> tools = new ArrayList<>();
    static boolean[] visited;
    static int tool_cnt;
    static int answer = Integer.MAX_VALUE;
    public int solution(int[] picks, String[] minerals) {
        for(int num : picks) {
            tool_cnt += num;
        }
        
        for(int i = 0; i < picks.length; i++) {
            for(int j = 0; j < picks[i]; j++) {
                if(i == 0) {
                    tools.add("diamond");
                } else if (i == 1) {
                    tools.add("iron");
                } else {
                    tools.add("stone");
                }
            }
        }
        visited = new boolean[tool_cnt];
        backtracking(0, 0, 0, minerals);
        return answer;
    }
    
    static public void backtracking(int depth, int score, int idx, String[] minerals) {
        if(idx == minerals.length || depth == tool_cnt) {
            answer = Math.min(answer, score);
            return;
        }

        for(int i = 0; i < tool_cnt; i++) {
            if(!visited[i]) {
                int temp = 0;
                int len = 0;
                visited[i] = true;
                
                if(idx + 5 >= minerals.length) {
                    len = minerals.length;
                } else {
                    len = idx + 5;
                }
                
                for(int j=idx; j < len; j++) {
                    if(tools.get(i).equals("diamond")) {
                        temp += 1;
                    } else if(tools.get(i).equals("iron")) {
                        if(minerals[j].equals("diamond")) {
                            temp += 5;
                        } else {
                            temp += 1;
                        }
                    } else {
                        if(minerals[j].equals("diamond")) {
                            temp += 25;
                        } else if(minerals[j].equals("iron")) {
                            temp += 5;
                        } else {
                            temp += 1;
                        }
                    }
                }
                backtracking(depth + 1, score + temp, len, minerals);
                visited[i] = false;
            }
        }
    }
    
}

 

3. 구현 로직

1. 곡괭이 수만큼 ArrayList에 저장
2. 어떤 곡괭이를 사용했는지를 체크하기 위해 방문 체크 배열 생성
3. 방문 체크를 통해 곡괭이를 1개 사용하고 한 번 사용하면 5개를 연속으로 캐야하므로 idx + 5
4. 다음 곡괭이를 사용하기 위해 backtracking 함수 실행
5. 어떤 곡괭이를 먼저 사용했는지 모르니까 방문 체크 해제

4. 유의할 점

• 실패 코드로 제출했을 때 시간초과가 났는데 생각을 해보니까 현재의 answer보다 score가 크거나 같으면 고려할 필요가 없었다.
• 그래서 score >= answer 조건을 추가하여 불 필요한 가지를 제거했다.