[Programmers] 광물 캐기

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

프로그래머스

 

1. 문제 설명

곡괭이와 광물에 따른 피로도 표

 

작업을 끝내기까지 필요한 최소한의 피로도를 구해야 한다.

작업을 끝내는 것은 1) 모든 광물을 캐거나, 2) 더 사용할 곡괭이가 없을 때까지이다.

곡괭이 하나를 선택하면 광물 5개를 연속으로 캘 수 있다.

2. 구현 아이디어 1 - 틀렸습니다

곡괭이 하나를 선택하면 광물 5개를 연속을 캘 수 있다고 했으니, 주어진 minerals 배열을 5개씩 나누어 생각해보았다.

글자색을 다르게 하여 각 구간을 다이아몬드 / 철 / 돌 곡괭이로 캤을 때 피로도를 아래에 적었다.

체크 표시는 피로도가 최소일 때, 해당 구간에서 선택한 곡괭이를 표시한 것이다.

 

예제 2에서 마지막 diamond는 캘 수 없다. picks 배열에 주어진 곡괭이가 총 2개이므로 광물은 10개까지만 캘 수 있으므로, 마지막 iron까지만 캐고 작업이 중단된다.

 

다이아몬드 > 철 > 돌 곡괭이 순으로 해당 곡괭이로 캤을 때 피로도가 큰 구간으로 곡괭이를 배치하는 방법을 떠올렸다.

즉, 좋은 곡괭이일수록 피로도가 높은 구간에 배치해야 한다.

 

예제 1에서 만약 연두색 구간에서 다이아몬드 곡괭이를 선택하면, 하늘색 구간에서 철 곡괭이나 돌 곡괭이를 사용해야 하기 때문에 피로도 총합이 커진다.

그러므로 하늘색 구간에서 다이아몬드 곡괭이를 선택해야 한다.

 

위 방법을 코드로 구현하기 위해서 필요한 작업은 아래와 같다.

1. 각 구간을 다이아몬드, 철, 돌 곡괭이로 캤을 때 피로도를 저장해야 한다  → tuple 자료형 사용
2. 피로도가 큰 순(다이아몬드, 철, 돌 순)으로 구간을 정렬해야 한다 → priority_queue 사용 (with 정렬 조건 커스텀)
3. 모든 광물을 캐거나 곡괭이를 모두 사용할 때까지 우선순위 큐에서 값을 꺼내 피로도를 계산하는 과정을 반복한다

#include <string>
#include <vector>
#include <tuple>
#include <queue>

using namespace std;

typedef tuple<int, int, int> tiii;

// 2번 과정: 피로도가 큰 순(다이아몬드, 철, 돌 순)으로 우선순위 큐 정렬
struct cmp {
    bool operator()(tiii a, tiii b) {
        if (get<0>(a) == get<0>(b)) {
            if (get<1>(a) == get<1>(b)) {
                return get<2>(a) < get<2>(b);
            } else {
                return get<1>(a) < get<1>(b);
            }
        }
        return get<0>(a) < get<0>(b);
    }
};

int solution(vector<int> picks, vector<string> minerals) {
    int answer = 0; // 피로도
    
    priority_queue<tiii, vector<tiii>, cmp> pq;
    
    // 1번 과정: 구간별 피로도 계산
    for (int i = 0 ; i < minerals.size(); i += 5) {
        int diamond = 0; // 다이아몬드 곡괭이로 캤을 때 피로도
        int iron = 0; // 철 곡괭이로 캤을 때 피로도
        int stone = 0; // 돌 곡괭이로 캤을 때 피로도
        
        for (int j = i; j < i + 5; j++) {
            // index out of range 방지
            if (j >= minerals.size()) break;
            
            if (minerals[j] == "diamond") {
                diamond += 1;
                iron += 5;
                stone += 25;
            } else if (minerals[j] == "iron") {
                diamond += 1;
                iron += 1;
                stone += 5;   
            } else { // minerals[j] == "stone"
                diamond += 1;
                iron += 1;
                stone += 1; 
            }
        }
        
        pq.push(make_tuple(diamond, iron, stone));
    }
    
    // 곡괭이 벡터(picks)를 순회하며 ...
    for (int i = 0; i < 3; i++) {
        
        // 해당 속성 곡괭이 없음
        if (picks[i] == 0) continue;
        
        while(picks[i]--) {
            // 모든 광물을 다 캤음
            if (pq.empty()) break;
            
            if (i == 0) answer += get<0>(pq.top());
            else if (i == 1) answer += get<1>(pq.top());
            else answer += get<2>(pq.top());
            
            pq.pop();
        }
    }
    
    return answer;
}

 

 

테스트케이스 8, 15, 34, 35에 실패하였다.

 

3. 구현 아이디어 2 - 정답입니다!

먼저 테스트 케이스 8번이 틀린 이유는 곡괭이로 채굴 가능한 수 < 광물의 수인 경우이다. 곡괭이로 채굴 불가능한 뒷부분 구간은 캘 필요가 없는데 우선순위 큐에 담아 우선순위가 높아지면 캐도록 계산이 된다.

 

위 코드에서 채굴 가능한 구간의 수는 picks 배열의 수를 다 합한 값이므로, pq의 원소의 개수가 picks 배열 원소의 합일 경우 pq에 원소를 추가하지 않도록 코드를 추가해주었다.

 

// 곡괭이로 채굴 가능한 구간 수 계산
int pickSum = 0;
for (int pick : picks) {
    pickSum += pick;
}

// pq의 원소의 개수가 picks 배열 원소의 합일 경우 pq에 원소를 추가하지 않음
if (pq.size() < pickSum) pq.push(make_tuple(diamond, iron, stone));

 

나머지 코드는 생략하고, 추가한 코드는 위와 같다.

 

다음 반례는 아래와 같다.

 

 

✅ 를 한대로 곡괭이를 선택해야 피로도가 최소가 된다.

하지만 내 코드의 경우 하늘색 구간에서 다이아몬드 곡괭이, 연두색 구간에서 돌 곡괭이를 선택하기 때문에 틀린다.

 

 다른 사람의 풀이를 참고하여 해결하였다. 우선순위 큐 원소를 정렬할 때, 돌 곡괭이로 캤을 때 피로도가 큰 순으로 정렬을 하고 그 순서대로 다이아몬드 > 철 > 돌 곡괭이를 선택해주는 것이다.

 

struct cmp {
    bool operator()(tiii a, tiii b) {
        return get<2>(a) < get<2>(b);
    }
};

 

우선순위 큐 정렬 함수를 위와 같이 수정하여 문제를 맞출 수 있었다.

 

---

우선순위 큐 정렬로 문제를 풀었는데, 입력의 최댓값이 작아 DFS(또는 성능 향상을 위해 백트래킹)으로 푼 풀이도 많았다.