[Programmers] Level 2 :: 과제 진행하기 C++ 풀이

프로그래머스

귀찮았던 구현 문제이다. 주어진 조건대로 구현을 하면 되는데 주의할 부분이 하나 있다. 
문제에서 요구하는 시뮬레이션 순서는 아래와 같다.

1. 시간이 되면 새로운 과제를 시작한다.
2. 새로운 과제를 수행할때, 기존에 수행하던 과제가 있으면 대기열로 해당 과제를 보낸다.
3. 현재 진행중인 과제가 끝이 나면, 대기중인 과제를 이어서 수행한다.

이렇게 케이스를 나눠볼 수 있다. 사실 케이스를 더 쪼갤 수 있지만, 새로운 과제가 있다면 무조건 시작해야 하기 때문에, 조건문 순서를 잘 걸어두면 간소화할 수 있다.

대기열에 들어간 과제는 가장 최근에 멈춘 과제부터 수행해야 한다. 그러므로, 이 대기열을 우선순위 큐로 관리하면 아주 간단하게 최근 과제를 꺼낼 수 있다.

주의 해야할 점은 시뮬레이션을 돌리는 구현을 했을때 존재하는데, 시간의 범위를 체크해야 한다. 과제를 마치는데 걸리는 시간은 최대 100분까지 소요되고, 과제의 수가 1000개이므로 시간은 100000까지 체크를 해줘야 한다. 

 

#include <string>
#include <vector>
#include <sstream>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
struct st {
    string name;
    int t;
    int l;
};

struct compare {
    bool operator() (const st s1, const st s2) {
        return s1.t < s2.t;
    }
};

priority_queue<st, vector<st>, compare> pq;
vector<st> v[200000];

vector<string> split(string input, char d) {
    stringstream ss(input);
    vector<string> result;
    string temp;
    while (getline(ss, temp, d)) {
        result.push_back(temp);
    }
    return result;
}

vector<string> solution(vector<vector<string>> plans) {
    vector<string> answer;
    int mini = 1e9;
    for (auto plan: plans) {
        st s;
        s.name = plan[0];
        s.t = stoi(split(plan[1], ':')[0]) * 60 + stoi(split(plan[1], ':')[1]);
        s.l = stoi(plan[2]);
        v[s.t].push_back(s);
        mini = min(mini, s.t);
    }
    
    string curr_name = v[mini][0].name;
    int start_time = mini;
    int end_time = mini + v[mini][0].l;
    
    for (int i=mini+1; i<200000; i++) {
        
        if (end_time == i) {
            answer.push_back(curr_name);
            curr_name = "";
            if (!pq.empty()){
                while (!pq.empty()) {
                    auto top = pq.top();
                    pq.pop();
                    curr_name = top.name;
                    start_time = i;
                    end_time = i + top.l;
                    break;
                }
            }
        }
        
        if (v[i].size() != 0) {
            if (curr_name != "") {
                st s;
                s.name = curr_name;
                s.t = i;
                s.l = end_time - i;
                pq.push(s);
            }
            curr_name = v[i][0].name;
            start_time = i;
            end_time = i + v[i][0].l;
        } 
    }
    
    while (!pq.empty()) {
        auto top = pq.top();
        pq.pop();
        answer.push_back(top.name);
    }
    
    return answer;
}