[프로그래머스/C++] Lv.2 과제 진행하기 로직 및 구현

문제

---

문제 설명

과제를 받은 루는 다음과 같은 순서대로 과제를 하려고 계획을 세웠습니다.

• 과제는 시작하기로 한 시각이 되면 시작합니다.
• 새로운 과제를 시작할 시각이 되었을 때, 기존에 진행 중이던 과제가 있다면 진행 중이던 과제를 멈추고 새로운 과제를 시작합니다.
• 진행중이던 과제를 끝냈을 때, 잠시 멈춘 과제가 있다면, 멈춰둔 과제를 이어서 진행합니다.
• 멈춰둔 과제가 여러 개일 경우, 가장 최근에 멈춘 과제부터 시작합니다.

과제 계획을 담은 이차원 문자열 배열 plans가 매개변수로 주어질 때, 과제를 끝낸 순서대로 이름을 배열에 담아 return 하는 solution 함수를 완성해주세요.

 

제한사항

• 3 ≤ plans의 길이 ≤ 1,000
• 진행중이던 과제가 끝나는 시각과 새로운 과제를 시작해야하는 시각이 같은 경우 진행중이던 과제는 끝난 것으로 판단합니다.

 

입출력 예

plans	result
[["korean", "11:40", "30"], ["english", "12:10", "20"], ["math", "12:30", "40"]]	["korean", "english", "math"]
[["science", "12:40", "50"], ["music", "12:20", "40"], ["history", "14:00", "30"], ["computer", "12:30", "100"]]	["science", "history", "computer", "music"]
[["aaa", "12:00", "20"], ["bbb", "12:10", "30"], ["ccc", "12:40", "10"]]	["bbb", "ccc", "aaa"]

 

---

문제 풀이

---

처음 내가 생각한 로직은 아래와 같은데 로직을 구현하려고 하니 생각보다 복잡해 start시간을 분단위로 계산해서 저장해두기로 했다.

그리고 지금이 몇분인지 확인하는 변수를 하나 따로 지정해 움직이기로 결정하였다.

 

사용한 트릭은 1분단위로 늘려가며 상황을 확인하기엔 혹시나 오랜 시간으로 터질 수도 있을 것 같아 바로 이후 상황이 몇분에 오는지 확인하며 문제를 처리하였는데 그렇게 처리하면 맨 마지막 상황에 exception이 생기므로 제약조건의 최대 24시간과 최대 작업시간보다 훨씬 큰 값을 넣어두고 사용하지 않는 방향으로 plans을 조금 손봤다.

1. 다음 것이 오기 전에 다 끝낸 경우
   
   1. 바로 정답에 넣기
   2. 남은 시간 없을 때까지 남는 시간 스택 맨 위 시간에서 빼주기
   3. 만약 스택 위에 작업을 완료했으면 빼고 다음 작업 진행을 반복
2. 다음 것이 오기 전에 다 못 끝낸 경우
   1. 스택 맨 위에 남은 시간으로 넣기
3. for문 돌고나면 stack 빼주면서 정답 뒤에 넣기.

구현 중에 스택이 빌 경우를 깜빡하고 놓쳐서 디버깅하느라 시간이 좀 걸려 대략 고민 20분 구현 40분정도로 구현에 생각보다 시간이 너무 걸린 문제이다.

---

코   드

---

#include <bits/stdc++.h>
using namespace std;

bool comp(vector<string> a, vector<string> b)
{
    return stoi(a[1]) < stoi(b[1]) ;
}

//this function change time(string) to minutes(string)
string time2mm(string st)
{
    auto minute =  to_string(stoi(st.substr(0,2)) * 60 + stoi(st.substr(3,5)));
    return minute ;
}

vector<string> solution(vector<vector<string>> plans) {
    vector<string> answer;
    stack<vector<string>> st ;
    
    for(auto &plan : plans)
        plan[1] = time2mm(plan[1]) ;
    
    sort(plans.begin() , plans.end(), comp) ;
    
    //plans의 맨 마지막에 임의의 값을 넣어서 기존 마지막값도 exception없이 처리하기 위함
    vector<string> tmp ;
    string str[] = {"LAST", "2000", "2000"} ;
    for(auto s : str)
        tmp.push_back(s);
    plans.push_back(tmp);

    for(int i = 0 ; i < plans.size() - 1 ; i++) {

		//바로 직전값과 비교해 작업을 완료할 수 있는지 확인
        int now = stoi(plans[i+1][1]) - (stoi(plans[i][1]) + stoi(plans[i][2])) ;

		//가능한 경우
        if(now >= 0) {
            answer.push_back(plans[i][0]) ;
            
            //작업을 완료하고도 여유시간이 있다면 반복해서 미뤄둔 작업 처리
            while(now > 0) {
                if(st.empty()) {
                    now = 0 ;
                    break ;
                }
                int top = stoi(st.top()[2]);
                
                if(now >= top) {
                    now -= top ;
                    answer.push_back(st.top()[0]) ;
                    st.pop() ;
                }
                else {
                    st.top()[2] = to_string(top - now) ;
                    now = 0 ;
                }
            }
        }
        //불가능한 경우 스택에 넣어두고 보류
        else {
            plans[i][2] = to_string(-now) ;
            st.push(plans[i]);
        }
    }
    //보류한 작업들 순서대로 완료
    while(!st.empty()) {
        answer.push_back(st.top()[0]);
        st.pop() ;
    }
    return answer;
}

---

느낀점: 30분안에 문제를 풀어내고 싶었는데 조금 어려웠던 것 같다.

링크: https://school.programmers.co.kr/learn/courses/30/lessons/176962?language=cpp 

프로그래머스