[알고리즘/C++] 프로그래머스 광물캐기

0. 개요

최근 풀었던 문제 중 다양한 알고리즘이 가능한 문제라 인상적
생각해볼 수 있는 모든 알고리즘을 고려한 후 시간 복잡도를 분석해보도록 한다.

1. 문제

• 곡괭이로 광물을 캐야하며, 이때 소요되는 '피로도'를 나타낸 표
• 곡괭이는 한 번 쓰면 "5개"의 광물을 캘 때까지 쓰고 사용 종료
• 광물은 주어진 순서대로만 캘 수 있음
• 광산에 있는 모든 광물을 캐거나, 더 사용할 곡괭이가 없을 때까지
• 최소 피로도를 계산

1) 입력

• 곡괭이의 개수 정보, 광물 캐는 순서

vector<int> picks, vector<string> minerals

• 최소 피로도 출력

2) 초기 아이디어

• 광물 캐는 순서는 '불변' 이므로, 곡괭이의 사용 순서가 핵심이라고 판단
• 그렇다면 곡괭이는 좋은 것(피로도가 낮은 것)부터 사용
• 다이아 > 철 > 돌 순으로 사용

3) 초기 코드

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int solution(vector<int> picks, vector<string> minerals) 
{
    int answer = 0;
    
    int dia, iron, stone;
    dia = picks[0];
    iron = picks[1];
    stone= picks[2];
    
    // 캐고자 하는 광물의 인덱스
    int idx = 0;
    
    // 다이아 > 철 > 돌 순으로 사용
    while (dia-- && idx < minerals.size())
    {
        for (int i = 0;i < 5;i++)
        {
            if (idx >= minerals.size())
                break;
            answer++;
            idx++;
        }
    }
    
    while (iron-- && idx < minerals.size())
    {
        for (int i = 0;i < 5;i++)
        {
            if (idx >= minerals.size())
                break;
            string mineral = minerals[idx];
            if (mineral == "diamond")
            {
                answer += 5;
            }
            else
                answer++;

            idx++;
        }
    }

    while (stone-- && idx < minerals.size())
    {
        for (int i = 0;i < 5;i++)
        {
            if (idx >= minerals.size())
                break;
            string mineral = minerals[idx];
            if (mineral == "diamond")
                answer += 25;
            else if (mineral == "iron")
                answer += 5;
            else
                answer++;
            idx++;
        }
    }
    cout << answer << endl;
    return answer;
}

• 초기 아이디어 치고, 다소 긴 코드이다. 어느정도 비효율성이 보이나, 정답을 맞춘 후 다듬으려 하였으나 실패

반례가 있다면, 그것은 최소 피로도가 "좋은 곡괭이부터 쓰는 것"이 아닌 경우에 발생하는 경우일 것이다.

c.f.
solution({ 1,1,0 },{ "stone", "stone", "iron", "stone", "diamond", "diamond", "diamond", "diamond", "diamond", "diamond" });

• 다이아, 철 순으로 사용한다면
  answer = 5 + 5 * 5 = 30
• 철, 다이아 순으로 사용한다면
  answer = (1+1+1+1+5) + 1 * 5 = 14

2. Solution - ①

1) 반례 분석

반례가 발생하는 이유는 피로도가 많이 드는 광물이 뒤에 위치한 경우 뒤에 남은 곡괭이(덜 좋은 곡괭이)를 사용하게 되므로

2) 반례 해결

• 그렇다면 5개씩 끊어서(어차피 곡괭이는 5개의 광물을 캘꺼니깐) 피로도의 합이 높은 곳에 좋은 곡괭이를 쓰도록 설계
• 5개로 이루어진 광물set의 피로도가 높은 순서대로 좋은 광물을 배정하도록

3) 2번째 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <stack>
using namespace std;

// 광물 별 피로도 순위를 매기기 위한 함수
int getVal(string mineral)
{
    if (mineral == "diamond")
        return 3;
    else if (mineral == "iron")
        return 2;
    else
        return 1;
}

// 곡괭이별 광물캐는 비용(피로도)
int countVal(string pick, string mineral)
{
    if (pick == "dia")
        return 1;
    else if (pick == "iron")
    {
        if (mineral == "diamond")
            return 5;
        else
            return 1;
    }
    else
    {
        if (mineral == "dia")
            return 35;
        else if (mineral == "iron")
            return 5;
        else
            return 1;
    }
}

int solution(vector<int> picks, vector<string> minerals) 
{
    int answer = 0;
    int dia = picks[0];
    int iron = picks[1];
    int stone = picks[2];
    stack<string> tool;
    
    // tot : 총 곡괭이의 수, tot_mineral : 총 캘 수 있는 광물의 수 
    int tot = dia + iron + stone;

    for (int i = 0;i < stone;i++)
        tool.push("stone");
    for (int i = 0;i < iron;i++)
        tool.push("iron");
    for (int i = 0;i < dia;i++)
        tool.push("dia");

    // 캘수 있는거
    int tot_mineral = tot * 5;
    // 캘 거
    int tot_minerals = minerals.size();

    int real = min(tot_mineral, tot_minerals);

    vector <pair<int,int>> sum_of_val;
    for (int i = 0;i < real;i+=5)
    {
        int sum = 0;
        int j;
        for (j = 0;j < 5;j++)
        {
            if (i+j >= real)
                break;
            sum += getVal(minerals[i + j]);
        }
        sum_of_val.push_back({sum,i });
    }

    sort(sum_of_val.begin(), sum_of_val.end(),greater<>());

    for (int i = 0;i < sum_of_val.size();i++)
    {
        int idx = sum_of_val[i].second;
        string pick = tool.top();
        tool.pop();
        if (idx + 5 < minerals.size())
        {
            for (int j = idx;j < idx + 5;j++)
            {
                answer += countVal(pick, minerals[j]);
            }
        }
        else
        {
            for (int j = idx;j < minerals.size();j++)
                answer += countVal(pick, minerals[j]);
        }
    }

    cout << answer << endl;
    return answer;
}

3. Solution - ③

1) 반례 분석

• 또 다른 반례가 발생하는 이유는 광물 집합이 3개, 곡괭이가 2개 있을 때, 광물 집합의 피로도와 별개로 '3번째 광물 집합'은 캘 수 없게되기 때문.
  즉 초기 조건인 "광물캐기는 무조건 minerals의 순서대로 라는 규칙에 위배

2) 반례 해결

• 캘 수 있는 광물 수가 캐려는 광물 수보다 작을 때의 조건 추가

3) 정답 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <stack>
using namespace std;

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

int countVal(string pick, string mineral)
{
    if (pick == "dia")
        return 1;
    else if (pick == "iron")
    {
        if (mineral == "diamond")
            return 5;
        else
            return 1;
    }
    else
    {
        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 dia = picks[0];
    int iron = picks[1];
    int stone = picks[2];
    stack<string> tool;
    vector<string>minerals2;
    
    // tot : 총 곡괭이의 수, tot_mineral : 총 캘 수 있는 광물의 수 
    int tot = dia + iron + stone;

    for (int i = 0;i < stone;i++)
        tool.push("stone");
    for (int i = 0;i < iron;i++)
        tool.push("iron");
    for (int i = 0;i < dia;i++)
        tool.push("dia");

    // 캘수 있는거
    int tot_mineral = tot * 5;
    // 캘 거
    int tot_minerals = minerals.size();

    int real = min(tot_mineral, tot_minerals);

    if (tot_minerals > tot_mineral)
    {
        for (int i = 0;i < tot_minerals;i++)
        {
            minerals2.push_back(minerals[i]);
        }
        minerals = minerals2;
    }

    vector <pair<int,int>> sum_of_val;
    bool isFit = true;
    for (int i = 0;i < real;i+=5)
    {
        int sum = 0;
        int j;
        for (j = 0;j < 5;j++)
        {
            if (i+j >= real)
                break;
            sum += getVal(minerals[i + j]);
        }
        sum_of_val.push_back({sum,i });
    }

    sort(sum_of_val.begin(), sum_of_val.end(),greater<>());

    for (int i = 0;i < sum_of_val.size();i++)
    {
        int idx = sum_of_val[i].second;
        string pick = tool.top();
        tool.pop();
        if (idx + 5 < minerals.size())
        {
            for (int j = idx;j < idx + 5;j++)
            {
                answer += countVal(pick, minerals[j]);
            }
        }
        else
        {
            for (int j = idx;j < minerals.size();j++)
                answer += countVal(pick, minerals[j]);
        }
    }

    cout << answer << endl;
    return answer;
}

4. Better Solution

(이 정도 난이도에 LOC가 100에 가깝다는 것은 상당히 비효율적인 요소가 만다는 것이므로, 계속해서 개선 할 예정 )

5. Other Solution

풀이 완료 후 서치를 해보니 다양한 솔루션을 사용할 수 있었다.

역시 Problem solving보다 어려운 것은 error locate와 반례 찾기 이다. 코드가 길어질수록 얼마나 내 코드를 짜임새 있게 이해하고 있는가가 중요하다.

[출처]
https://school.programmers.co.kr/learn/courses/30/lessons/172927