프로그래머스 - 광물 캐기 (C++)

1. 문제 링크

코딩테스트 연습 - 광물 캐기

2. 소스코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int chart[3][3]={
    {1,1,1},
    {5,1,1},
    {25,5,1}
};

int solution(vector<int> picks, vector<string> minerals) {
    int answer=0;
    vector<int> temp;
    vector<vector<int>> unit;
    //곡괭이 수 계산
    int cnt=0;
    for(int p:picks)cnt+=p;
    for(int i=0;i<minerals.size();i++){
        if(i==cnt*5){
            //주어진 곡괭이로 더 캘 수 없기 시작
            unit.push_back(temp);
            break;
        }
        if(i%5==0){
            if(i!=0)unit.push_back(temp);
            temp=vector<int>(3,0);
        }
        //종류별로 세기
        if(minerals[i]=="diamond")temp[0]++;
        else if(minerals[i]=="iron")temp[1]++;
        else temp[2]++;
    }
    //곡괭이 공급이 더 많을 때
    if(minerals.size()<=5*cnt)unit.push_back(temp);
    //내림차순 정렬
    sort(unit.rbegin(),unit.rend());
    //앞에서부터 다이아몬드-철-돌 곡괭이 할당
    int index=0;
    for(vector<int> v:unit){
        //곡괭이 할당
        while(index<2&&picks[index]<=0)index++;
        //더이상 쓸 수 있는 곡괭이 없음
        if(picks[index]<=0)break;
        picks[index]--;
        //피로도 계산
        for(int i=0;i<3;i++){
            answer+=v[i]*chart[index][i];
        }
    }
    return answer;
}

3. 노트

3-1.백트래킹으로 접근

광물의 개수가 최대 50개이므로, 곡괭이는 최대 10개까지 사용된다. 사용하는 곡괭이의 순서의 경우의 수는 최악의 경우 10!/(3!*3!*4!) 이므로 이를 dfs-백트래킹으로 구현하려 하였지..만! 막상 함수를 만드려니 복잡해서 그냥 하기가 싫었음.

3-2.Greedy로 접근

이 문제는 탐욕법으로 푸는 게 더 간단하다.
우선 피로도를 계산하는 표를 보면, 곡괭이 성능은 다이아몬드>철>돌 순으로 좋고, 피로도가 많이 쌓이는 광물 순서 역시 다이아몬드>철>돌 순이다.
그럼 다이아몬드가 많이 포함된 묶음일수록 좋은 성능의 곡괭이를 써야겠지?

앞에서부터 다섯 개의 광물을 한 세트로 묶어, 다이아몬드, 철, 돌의 개수를 센 후, 모든 묶음을 다이아몬드, 철, 돌의 개수 순으로 내림차순 정렬하여, 앞에서부터 성능이 좋은 곡괭이를 할당하면 되는 것이다.

3-3.고려할 점(edge case)

광물을 앞에서부터 다섯 개씩 묶을 때, 곡괭이의 개수도 고려해야 한다.
광물은 순서대로 캐야 하므로, 곡괭이의 개수가 광물에 비해 모자랄 경우 뒷 순서 광물들은 캘 수 없다.
이를 고려하지 않고, 모든 광물을 다섯 개씩 묶은 후 내림차순 정렬을 실행하면, 상황에 따라서 뒷 순번이여서 캘 수 없는 광물들이 앞쪽으로 정렬되어 버린다.
이를 고려하여 캘 수 있는 광물의 총량보다 뒷 순번인 경우, 다섯 개씩 묶는 것을 중단하여야 하겠다.

3-4.내가 고려할 점

보통 반복문이 종료된 후 짬처리(?)를 해 줘야 하는 경우가 많은데,
이 문제의 경우
1) 곡괭이로 캘 수 있는 총량보다 광물의 양이 적을 때
2) 곡괭이로 캘 수 있는 총량보다 광물의 양이 많을 때
3) 딱 떨어질 때
이 세 가지 경우를 잘 고려하여 짬처리 코드를 작성해야 하겠다^^..