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

스택에 대한 이해가 필요했던 문제.

문제 설명

문제에서 추출할 수 있는 정보는 다음과 같다.

• 입력되는 과제 배열은 시간 오름차순으로 정렬해야 한다.
• 현재 과제 종료시각과 다음 과제 시작시각이 동일하면 진행중이던 과제는 끝난 것으로 간주한다.
• 현재 과제는 다음 과제의 진행 시각이 될 때까지 완료되지 못하면 중단된다.
• 중단된 과제들은 스택 형태로 보관되어야 한다.
  ("멈춰둔 과제가 여러 개일 경우 최근에 멈춘 과제부터 시작한다")
• 현재 과제의 종료시각부터 다음 과제의 시작시각까지 시간이 남았을 때 스택에서 중단된 과제를 꺼내어 다시 수행할 수 있다.

해결 과정

먼저 시간 문자열을 편리하게 다루기 위해 시간을 분 단위의 정수로 변환했으며, 본 로직에 들어가기 전 시간 오름차순 정렬을 수행한다.

int getTime(string time1){ // 시간 문자열을 정수값으로 변환
    int hour1 = stoi(time1.substr(0, 2));
    int minute1 = stoi(time1.substr(3, 2));
    return hour1*60 + minute1;
}

bool cmp(vector<string> v1, vector<string> v2){ // 시간 오름차순 정렬
    return getTime(v1[1]) < getTime(v2[1]);
}

또한 스택에 들어가야 할 정보는 <중단된 과제의 잔여 시간, 중단된 과제의 이름> 이다.

이제 본 로직을 설계해보자.

(1) 시작시각이 정해진 "다음 과제"가 있을 때 (index < 과제수-1)

• (a) 현재 과제의 종료시각 > 다음 과제의 시작시각
  -> 다음 과제의 시작시각까지는 진행한 뒤, 잔여시간+이름을 스택에 담고 다음 과제를 수행

• (b) 현재 과제의 종료시각 = 다음 과제의 시작시각
  -> 중단된 과제보다 다음 과제가 우선이기 때문에 다음 과제를 바로 수행
  

• (c) 현재 과제의 종료시각 < 다음 과제의 시작시각
  -> 현재 과제의 종료시각에서 스택에서 하나씩 중단된 과제의 잔여 시간을 더해나가며 다음 과제의 시작시각 이전까지 수행
  참고로 if문이 아니라 while문임에 주의한다. (16분이 비어있고 중단된 과제가 5분/10분이라면 둘 다 수행할 수 있기 때문이다.)**

(2) 다음 과제가 더 이상 없을 때
-> 스택에 담긴 중단된 과제들을 모두 빼내고 로직을 종료한다.

소스 코드

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

using namespace std;
stack<pair<int, string>> s;

int getTime(string time1){ // 시간 문자열을 정수값으로 변환
    int hour1 = stoi(time1.substr(0, 2));
    int minute1 = stoi(time1.substr(3, 2));
    return hour1*60 + minute1;
}

bool cmp(vector<string> v1, vector<string> v2){ // 시간 오름차순 정렬
    return getTime(v1[1]) < getTime(v2[1]);
}

vector<string> solution(vector<vector<string>> plans) {
    vector<string> answer;
    sort(plans.begin(), plans.end(), cmp);
    int i = 0;
    while(1){
        if(i == plans.size()-1) {
            answer.push_back(plans[i][0]);
            while(!s.empty()){
                answer.push_back(s.top().second);
                s.pop();
            }
            break;
        }
        
        if(i < plans.size()-1){
            string name = plans[i][0];
            string time = plans[i][1];
            string len = plans[i][2];
            int endTime = getTime(time) + stoi(len);
            int nextTime = getTime(plans[i+1][1]);
            int gap = endTime - nextTime;
            if(gap > 0){ // 중간에 중단해야 하는 과제
                s.push({gap, name}); // (완료까지 남은 시간, 이름)
                i++;
            } else { // 중단하지 않고 완료됨 -> 스택 확인해야함
                answer.push_back(name);
                if(gap == 0) { // 바로 다음 과제가 붙어있는 경우 스택 여부와 상관없이 다음 과제로 이동
                    i++;
                } else { // 중단된 과제가 있을 때
                    while(!s.empty()){
                        pair<int, string> now = s.top();
                        s.pop();
                        if(endTime + now.first <= nextTime){
                            answer.push_back(now.second);
                            endTime += now.first;
                            if(endTime == nextTime){
                                break;
                            }
                        } else {
                            s.push({endTime+now.first-nextTime, now.second});
                            break;
                        }
                    }
                    i++;
                } 
            }
        } 
    }    
    return answer;
}

교훈

• 스택과 같은 변칙적인 자료구조를 활용할 때는 while문을 바탕으로 한 흐름 제어가 편리할 때가 있으니, 항상 for문과 while문 중 유불리에 따라 정하도록 하자.
• 복잡한 흐름제어가 필요한 문제는 침착하게 예외상황을 판단하고 꼼꼼하게 처리하자.