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

Key

그리디로 풀 수 있는 구현문제

조건을 꼼꼼히 고려해야한다.

특히 곡괭이로 채굴 가능한 범위보다 광물 수가 더 많을 수 있다는 점을 유의해야한다.

 

Idea

1. minerals 배열을 5개 단위로 끊고 광물별 가중치를 줘서 그룹별 가중치 합을 구한다. (getScore 함수)

2. 그리고 그룹별 가중치 합과 시작 인덱스(5개 단위 그룹의 시작인덱스)를 group에 저장한다.

3. 가중치 합을 기준으로 내림차순 정렬한다. 이렇게 하면 캐기 어려운 광물이 많은 그룹일수록 앞으로 오게 된다.

4. 이제 그룹을 탐색하며 그룹의 시작 인덱스를 기준으로 minerals 배열에서 5개 단위로 피로도를 계산하면 된다. 캐기 어려운 광물이 많은 그룹이 앞으로 왔으므로 좋은 곡괭이부터 쓰면 최소한의 피로도가 보장된다.

 

주의할 점이 두가지 있다.

첫번째는 광물 총 개수가 5배수가 아닐 수 있다는 점. 나는 for문 조건식에 min(i+5, 광물 총 개수)를 둬서 주어진 인덱스 범위를 벗어나는 에러를 방지했다.

 

두번째는 곡괭이로 채굴 가능한 범위보다 광물 수가 더 많을 수 있다는 점이다.

이 조건을 고려하지 않는다면 8번 케이스에서 틀리게 된다.

예를 들어, 곡괭이가 하나뿐이라 5개밖에 채굴 못하는데 광물이 ["iron", "iron", "iron", "iron", "iron","diamond", "diamond"] 라면, 앞에서부터 차례대로 캐야하므로 결국 iron 5개만 채굴할 수 있다.

하지만 내 아이디어대로라면 diamond 두개를 캐게 될 것이다.

나는 이 조건을 생각하지 못해서 처음에 틀렸는데, 만약 곡괭이로 채굴 가능한 범위 < 광물 수 라면 minerals 배열의 길이를 곡괭이로 채굴 가능한 범위와 같아지게 잘라주었다. 

 

 

Code

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

using namespace std;

int getScore(string mineral){
    if(mineral=="diamond") return 25;
    else if(mineral=="iron") return 5;
    else return 1;
}

int solution(vector<int> picks, vector<string> minerals) {
    int answer = 0;
    int pickCnt=0;
    int mineralSize=minerals.size();
    
    vector<pair<int, int>>group;
    
    for(int pick : picks) pickCnt+=pick;
    
    int maxMineralSize=pickCnt*5;
    
    if(maxMineralSize < mineralSize) {
        minerals.erase(minerals.begin()+maxMineralSize, minerals.end());
        mineralSize=minerals.size();
    }
    
    // 광석 배열 5개씩 잘라서 어떤 광석이 많은지 파악
    for(int i=0; i<mineralSize; i+=5){
        int score=0;
        for(int j=i; j<min(mineralSize,i+5); j++){
            score+=getScore(minerals[j]);
        }
        group.push_back({score, i});
    }
    
    sort(group.rbegin(), group.rend());
    
    // 곡괭이 배정
    for(int i=0; i<group.size(); i++){
        int startIdx=group[i].second;
        if(picks[0]>0){
            for(int j=startIdx; j<min(mineralSize, startIdx+5); j++){
                answer+=1;
            }
            picks[0]--;
        }
        else if(picks[1]>0){
             for(int j=startIdx; j<min(mineralSize, startIdx+5); j++){
               if(minerals[j]=="diamond") answer+=5;
                else answer+=1;
            }
            picks[1]--;
        }
        else if(picks[2]>0){
             for(int j=startIdx; j<min(mineralSize, startIdx+5); j++){
                if(minerals[j]=="diamond") answer+=25;
                 else if(minerals[j]=="iron") answer+=5;
                 else answer+=1;
            }
            picks[2]--;
        }
        else break;
    }
    
    return answer;
}