[C++] 과제 진행하기

[문제]

코딩테스트 연습 - 과제 진행하기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

[문제풀이]

우선 첫번째로 string으로 받아오는 배열을 int(작업 시작시간), string(작업 이름), int(작업 진행시간) 으로 나누어서 배열에 집어넣었다.

*여기서 시작시간은 시 * 60 + 분 으로 계산을 하였다. 

그 뒤에 stack을 활용해 배열에 넣어져있는 작업들을 처음부터 끝까지 해당 조건에 따라서 stack에 넣다가 조건에 주어진 부분에 따라서 stack에서 빼고 answer에 넣는 경우도 발생한다.(자세한 것은 코드 참고)

만약 마지막에 stack안에 작업이 있다면 처음부터 끝까지 빼면서 answer에 넣는다.

[회고]

구현도 어렵고 풀이도 쉽지 않고 레벨2이지만 개인적으로 레벨3 문제들보다도 풀기가 더 힘들었다.

문제를 제대로 이해하지 못해서 상당히 어렵게 진행을 했었다.

최근에 중단된 작업이란 말을 제대로 이해하지 못하고 queue에 넣었다가 계속해서 문제가 발생하였고 이에 다른 사람의 코드를 보고 참고하였다.

비슷한 유형이 프로그래머스에서 유독 많은것 같다. 비슷한 유형들을 풀면서 연습하도록 하자.

[코드]

#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <iostream>
#include <sstream>

using namespace std;

//split 함수를 이용해서 string안에 들어있는 내용을 숫자로 바꿔주자. 시간 * 60 + 분 더해주기.
int split(string s){
    int answer = 0;
    string buffer;
    istringstream iss(s);
    char delimeter = ':';
    vector<string> result;
    while(getline(iss,buffer,delimeter)){
        result.push_back(buffer);        
    }
    answer = stoi(result[0]) * 60 + stoi(result[1]);
    return answer;
}

vector<string> solution(vector<vector<string> > plans){
    vector<string> answer;
    //plans 안에 있는 내용을 변환해서 넣어줄 배열.
    vector<pair<int, pair<string,int> > > times;
    for(int i = 0;i<plans.size();i++){
        pair<int,pair<string,int> > temp;
        temp.first = split(plans[i][1]);
        temp.second.first = plans[i][0];
        temp.second.second = stoi(plans[i][2]);
        times.push_back(temp);
    }
    //정렬해주자.
    sort(times.begin(),times.end());
    //작업들이 한번씩 들리는 스택
    stack<pair<int, pair<string,int> > > stop;
    
    int n = plans.size();

    for(int i = 0;i<n;i++){
        //stack에 작업이 있고 해당 작업의 종료시간보다 다음 작업 시작시간이 느리다면
        while(stop.size() > 0 && stop.top().first + stop.top().second.second <= times[i].first){
            //현재 작업 시작 시간 + 종료시간을 더해주자.
            int now = stop.top().first + stop.top().second.second;
            //answer에 넣어주자.
            answer.push_back(stop.top().second.first);
            //stack에서 제거.
            stop.pop();
            //만일 stack 사이즈가 0보다 크다면
            if(stop.size() > 0){
                //stack의 제일 위에 있는 작업 시작 시간을 현재 시간으로 바꿔주자.
                //이렇게 될 경우에 작업 시작 시간은 바뀌고 진행 시간은 안 바뀌니 종료 시간에 문제가 생기지 않나? 의문이 들 수 있는데
                //해당 문제는 이 아래 코드에서 해결이 된다.
                stop.top().first = now;
            }
        }
        //만일 다음에 들어올 시간보다 현재 작업시작 시간 + 진행될 시간이 크다면
        //현재 작업의 진행될 시간에서 다음 작업 시작 시간 - 현재 작업 시작시간을 빼주자.
        //이렇게 될 경우 12시 30분 시작, 100분 걸리는 작업 뒤에 12시 40분, 50분 작업 시간이 있다면
        //12시 30분 시작하는 작업은 앞으로 90분만 더 작업을 하면 종료가 되게 바뀐다.
        if(stop.size() > 0 && stop.top().first + stop.top().second.second > times[i].first){
            stop.top().second.second -= times[i].first - stop.top().first;
        }
        //언제나 stack위에 다음 시간 작업물을 추가하자.
        stop.push(times[i]);
    }
    //만일 전부 종료했는데 stack에 작업이 남아있다면 stack 작업을 모두 차례대로 빼주자.
    while(stop.size() > 0){
        answer.push_back(stop.top().second.first);  
        stop.pop();
    }

    return answer;
}