[JAVA] 프로그래머스 level2 광물 캐기

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

프로그래머스

코딩테스트 연습 > 연습문제 > 광물 캐기

 

문제 접근 

백트래킹 문제!!

 

1. 백트래킹을 통해서 곡갱이 사용 순서를 정한다. 

2. 사용 순서에 맞게 피로도 계산 

3. 가장 적은 피로도 return 

 

init data 백트래킹에 필요한 데이터 정리 하기

 

개인적으로 메서드에 매개변수를 많이 던지는 걸 싫어해서 static 으로 다시 저장하는 걸 선호한다.

특히 백트래킹 같은 경우 메서드 호출 횟수가 많은데 매개변수를 많이 넣으면 
그만큼 스택 프레임에 변수들이 많이 생기고 동일한 데이터가 계속 스택 프레임에 할당되는 게 아깝다고 생각한다. 

하지만 코딩 테스트에서는 굳이 이런 부분까지 신경을 쓰지 않아도 되고 취향껏 하면 된다. 

 

picks, minerals -> pick, mineral 

minerals 개수 -> size 

곡갱이 개수 -> count

int [] order 곡갱이 순서를 기록 용도

int [] memo 곡갱이 선택 상태  

    static int [] memo = new int [3];
    static int [] order;
    static int [] pick;
    static String [] mineral;
    static int size;
    static int count;
    static int min = Integer.MAX_VALUE;
    public int solution(int[] picks, String[] minerals) {
        pick = Arrays.copyOf(picks, 3);
        mineral = Arrays.copyOf(minerals, minerals.length);
        size = minerals.length;
        
        for(int cur : picks){
            count += cur;
        }
        
        order = new int [count];
        backTracking(0);
        
        return min;
    }

 

백트래킹을 통해서 곡갱이 사용 순서를 정하기

 

곡갱이 종류는 다이아, 철, 돌 3개다.

이미 각 곡갱이 개수를 pick으로 copy 하였다.

곡갱이를 선택할 때마다 memo에 해당 곡갱이 count를 증가해 주고 order에 넣어준다. 

종료 조건은 모든 곡갱이를 선택 완료했을 때다 즉 cnt == count

그리고 피로도 계산 메서드를 호출한다. calculate()

backTracking(0);

public static void backTracking(int cnt){
     if(cnt == count){
         calculate();
         return;
     }
     for(int i = 0; i < 3; i++){
         if(memo[i] < pick[i]){
             memo[i]++;
             order[cnt] = i;
             backTracking(cnt+1);
             memo[i]--;
         }
     }
}

 

피로도 계산 

 

order 배열에는 곡갱이가 선택한 순서대로 들어가 있다. 

곡갱이는 항상 5번 사용 가능하다. 

그래서 2중 for문 조건을 보면 5씩 증가하도록 만들었다. 

 

중요!! 곡갱이를 사용 가능한 횟수보다 광석이 적은 case가 있다. 

그런 경우 현재까지 누적한 피로도 sum을 비교하고 return 한다. 

이런 조건을 설정 안 하면 runtime 에러인 ArrayIndexOutOfBoundsException 가 발생한다. 

 

다이아 곡갱이는 항상 피로도 1 

철 곡갱이는 다이아만 피로도 5 나머지 1

돌 곡갱이는 다이아 25 철 5 돌 1 

 

누적해준다. 

 

곡갱이를 전부 사용했으면 그동안 누적한 피로도 값을 비교한다.  

public static void calculate(){
    int sum = 0;
    for(int i = 0; i < count; i++){
        int cur = order[i]; // 현재 곡갱이  
        // 곡갱이는 5번 사용 가능 
        for(int j = i * 5; j < (i * 5) + 5; j++){
            if(j == size){
                if(min > sum) min = sum;
                return;
            }
            if(cur == 0) sum++;
            else if(cur == 1){
                if(mineral[j].equals("diamond")){
                    sum += 5;
                }
                else sum++;
            }
            else{
                if(mineral[j].equals("diamond")){
                    sum += 25;
                }
                else if(mineral[j].equals("iron")){
                    sum += 5;
                }
                else sum++;
            }
        }
    }
    if(min > sum) min = sum;
}

 

전체 코드

import java.util.*;
class Solution {
    static int [] memo = new int [3];
    static int [] order;
    static int [] pick;
    static String [] mineral;
    static int size;
    static int count;
    static int min = Integer.MAX_VALUE;
    public int solution(int[] picks, String[] minerals) {
        pick = Arrays.copyOf(picks, 3);
        mineral = Arrays.copyOf(minerals, minerals.length);
        size = minerals.length;
        
        for(int cur : picks){
            count += cur;
        }
        
        order = new int [count];
        backTracking(0);
        
        return min;
    }
    public static void backTracking(int cnt){
         if(cnt == count){
             calculate();
             return;
         }
         for(int i = 0; i < 3; i++){
             if(memo[i] < pick[i]){
                 memo[i]++;
                 order[cnt] = i;
                 backTracking(cnt+1);
                 memo[i]--;
             }
         }
    }
    public static void calculate(){
        int sum = 0;
       
        for(int i = 0; i < count; i++){
            int cur = order[i]; // 현재 곡갱이 
            // 곡갱이는 5번 사용 가능 
            for(int j = i * 5; j < (i * 5) + 5; j++){
                if(j == size){
                    if(min > sum) min = sum;
                    return;
                }
                
                if(cur == 0) sum++;
                else if(cur == 1){
                    if(mineral[j].equals("diamond")){
                        sum += 5;
                    }
                    else sum++;
                }
                else{
                    if(mineral[j].equals("diamond")){
                        sum += 25;
                    }
                    else if(mineral[j].equals("iron")){
                        sum += 5;
                    }
                    else sum++;
                }
            }
        }
        if(min > sum) min = sum;
    }
}

 

아마 그리디로도 푸는 게 가능해 보인다. 

광석들의 구간(5씩)으로 구하고 가장 많이 비용이 드는 구간부터 다이아, 철, 돌 순서대로 사용하면 될듯하다. 

 

읽어주셔서 감사합니다!