[c++] 프로그래머스 :: 라면공장 (문제 풀이, 코드)

라면공장

https://programmers.co.kr/learn/courses/30/lessons/42629#

 

코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<pair<int, int>> node;

int solution(int stock, vector<int> dates, vector<int> supplies, int k) {
    int answer = 0;

    int day = stock;

    int size = dates.size();
    for (int i = 0; i < size; i++) {
        node.push_back(make_pair(dates[i], supplies[i]));
    }

    while (day < k) {
        int idx = 0;
        int max_idx = 0;
        while (idx < node.size() && node[idx].first <= day) {
            if (node[idx].second > node[max_idx].second) {
                max_idx = idx;
            }
            idx++;
        }
        day += node[max_idx].second;
        answer++;
        node.erase(node.begin() + max_idx);
    }

    return answer;
}

int main() {
    int stock = 7;
    vector<int> dates = { 3, 10, 12, 19 };
    vector<int> supplies = {3, 9, 12, 11 };
    int k = 30;
    cout << solution(stock, dates, supplies, k); //3
}

 

설명

 자료구조 힙 문제에 속해있는 문제이다. 이미 dates는 오름차순으로 정렬되어있다고 문제에 기재되어있으므로, 차례로 vector에 넣어주면 부분 정렬 뿐만 아니라 전체 정렬이 되어있는 힙 구조를 vector로 나타낸 셈이다. 그렇다면 해당 vector는 dates에 대한 최소 힙이 된다.

 사실 여기서 트리 구조로 따라 내려가면서 비교를 했으면 힙을 사용하였다고 우길수라도 있겠지만... index를 하나씩 증가시키면서 사용하였기 때문에 힙을 사용했다고 볼 수가 없다. 오름차순 정렬되어있는 배열을 사용한 것 뿐이다.

 

 

 어쨌든 문제 풀이를 해보면, 우선 처음 주어진 stock를 day에 저장한다. node에는 dates 오름차순으로 (dates, supplies)가 저장되어있다.

int day = stock;

int size = dates.size();
for (int i = 0; i < size; i++) {
    node.push_back(make_pair(dates[i], supplies[i]));
}

 

 

dates가 day를 넘지 않으면서 supply가 가장 큰 날짜를 찾는다. 찾았으면 현재 가지고 있는 밀가루가 소진되는 날짜인 day에 supply를 더해주고, 해당 dates를 node vector에서 삭제한다. 이 때마다 answer에 1씩 더해준다.

while (idx < node.size() && node[idx].first <= day) {
            if (node[idx].second > node[max_idx].second) {
                max_idx = idx;
            }
            idx++;
}
day += node[max_idx].second;
answer++;
node.erase(node.begin() + max_idx);

이런식으로 반복하다보면 주어진 k보다 day가 더 커지는 순간이 오는데, 그 때의 answer가 문제의 정답이다.

while (day < k) {
 //...
}

return answer;

 

채점 결과

 

다른 사람의 풀이

 힙 구조를 만들기 위해 우선순위큐를 사용한다는 걸 개념정리에서 했지만 생각해내지 못했다. STL 라이브러리에서 우선순위큐를 가져와 사용한 코드들이 많다.

 하루가 지날 때마다 stock이 감소하는 걸 보이기 위해 for문으로 k만큼을 반복하였다. dates에 해당하는 날이 오면 supply를 우선순위큐에 저장해둔 후, stock이 0이 될 때 불러와서 stock에 더해준다. 우선순위큐에 저장해둔 덕분에 supply가 큰 순서대로 빠져나오게 할 수 있다.