프로그래머스 - 광물 캐기 순열?, 그리디?

프로그래머스 광물캐기 java

관찰

일단 문제는 간단하다, 곡괭이 갯수가 주어지고 순서를 잘 맞춰서 최소의 피로도로 주어진 광물을 다 캘 수 있도록 하는 것이 문제

이 문제를 보고 15개의 순열 vs 그리디 라는 생각을 했고 그리디로 풀기 싫어서 순열로 도전을 해보았다.

---

정답 코드

문제를 풀기까지 2번의 시행착오를 겪었다. 그냥 순열 (perm), 비트 순열(bitperm), 중복 제거 순열(fastPerm) 그리고 각각의 시간을 체크해보았다.

import java.io.*;
import java.util.*;

class Solution {
    
    static int[][] piro = { {1,1,1}, {5,1,1}, {25,5,1}};
    static int n, min, m;
    static ArrayList<Integer> cnts;
    static int[] mines;
    static int[] pick;
    static boolean[] visited;
    public int solution(int[] picks, String[] minerals) {
        
        n = 0;
        cnts = new ArrayList<>();
        m = minerals.length;
        mines = new int[m];
        
        for(int i=0;i<3;i++){
            for(int j=0;j<picks[i];j++){
                if(i == 0){
                    cnts.add(0);
                }
                else if(i == 1){
                    cnts.add(1);
                }
                else{
                    cnts.add(2);
                }
            }
            n += picks[i];
        }
        pick = new int[n];
        visited = new boolean[n];
        
        for(int i=0;i<m;i++){
            if(minerals[i].equals("diamond")){
                mines[i] = 0;
            }
            if(minerals[i].equals("iron")){
                mines[i] = 1;
            }
            if(minerals[i].equals("stone")){
                mines[i] = 2;
            }
        }
        
        min = Integer.MAX_VALUE;
        
        //perm(0);
        bitperm(0,0);
        //fastPerm(0);
        
        
        return min;
    }
    
    static void perm(int depth){
        if(depth == n){
            int idx = 0;
            int count = 0;
            for(int i=0;i<n;i++){
                for(int j=0;j<5;j++){
                    if(idx >= m) continue;
                    count += piro[pick[i]][mines[idx++]];
                }
            }
            if(min > count) min = count;
            return;
        }
        
        for(int i=0;i<n;i++){
            if(!visited[i]){
                visited[i] = true;
                pick[depth] = cnts.get(i);
                perm(depth+1);
                pick[depth] = 0;
                visited[i] = false;
            }
        }
    }
    
    static void bitperm(int depth, int bit){
        if(depth == n){
            int idx = 0;
            int count = 0;
            for(int i=0;i<n;i++){
                for(int j=0;j<5;j++){
                    if(idx >= m) continue;
                    count += piro[pick[i]][mines[idx++]];
                }
            }
            if(min > count) min = count;
            return;
        }
        
        for(int i=0;i<n;i++){
            if((bit & (1 << i)) == 0){
                pick[depth] = cnts.get(i);
                bitperm(depth+1, bit | (1<<i));
                pick[depth] = 0;
            }
        }
    }
    
    static void fastPerm(int depth){
        if(depth == n){
            int idx = 0;
            int count = 0;
            
            for(int i = 0; i < n && idx < m; i++){
                for(int j = 0; j < 5 && idx < m; j++){
                    count += piro[pick[i]][mines[idx++]];
                }
            }
            
            min = Math.min(min, count);
            return;
        }
        
        int lastUsed = -1; // 중복 방지
        for(int i = 0; i < n; i++){
            if(!visited[i] && cnts.get(i) != lastUsed){
                lastUsed = cnts.get(i);
                visited[i] = true;
                pick[depth] = cnts.get(i);
                fastPerm(depth + 1);
                visited[i] = false;
            }
        }
    }
}

그냥 순열 결과

비트 순열 결과

중복 제거 순열 결과 (정답)

---

풀이

문제를 푸는 방식은 간단하다 곡괭이를 순열을 돌리고 결과중에 최소값을 return 해주면 된다.

일반 순열은 12개만 되어도 12! 이기 때문에 5억정도라서 5초정도가 걸린다 그래서 탈락

비트 순열은 사실 조금은 빨라질 줄 알았는데 결과에서도 볼 수 있듯이 거의 차이가 없었다. 그 이유를 claude에게 물어봤는데 9개 원소 기준: 일반 21.9ms vs 비트 19.2ms (1.14배 차이) 라고 한다..ㅋㅋ

사실 생각해보면 당연한 것 같다. 시간이 느는 핵심은 알고리즘이고 일반 순열하고 똑같이 돌아가기 때문이다. (CPU와 컴파일러가 너무 똑똑해서 차이가 없음)

그렇게 마지막 방법을 찾았는데 중복제거 순열로 해결하였다.

일단 곡괭이가 5,5,5 개씩 최대로 오기 때문에 15! 이지만 중복제거순열로 15!/ (5! 5! 5!) = 756,756 으로 빠르게 최적화가 가능하다!

핵심 로직은 동일한 depth에서 lastUsed를 저장해주면서 사용되었으면 들어가지 않는 것이다. 이런 식으로 시간복잡도를 줄여서 해결할 수 있었다.

---

마무리

사실 이 문제는 그리디였다.. 풀고 나서 다른 사람들 풀이를 보니깐 그리디로 엄청 빨리 풀 수 있는 문제였다. 5개씩 광물을 묶고 좋은 광물 순으로 정렬을 한 뒤 좋은 곡괭이로 먼저 캐주면서 푸는 좋은 풀이가 있었다..

정말 다행히도 곡괭이의 최대 갯수가 5개씩이라서 겨우 통과했지 6개만 되어도 순열로는 절대 못 풀었을 것이다. 그래도 순열을 다시 복습할 수 있어서 좋은 문제였던 것 같습니다!