문제 풀이 과정을 공유하고자 한다.
문제 출처

1. 문제설명

[과목, 시작 시간, 소요 시간]이 문자열 벡터로 여러개 주어짐.
- 정렬되지 않음!
과제 해결 프로세스
- 과제를 시작하다가, 새로운 과제의 시간이 되면 중간에 멈추고 새로운 과제 시작
- 진행중이던 과제를 끝내고, 멈춘 과제를 이어서 진행
  - 만약 멈춘 과제와 새로운 과제가 둘다 있다면, 새로운 과제부터 진행
  - 멈춘 과제가 여러 개면, 가장 최근에 멈춘 과제부터 진행

2. 알고리즘 설계

시작 시간에 따라 정렬
- priority_queue in <queue>
멈춘 과제는 가장 최근에 멈춘 과제부터 진행하므로, stack 구조 사용

우선순위 큐를 위한 구조체 선언

class는 범위지정연산자 default가 private이지만, struct는 public이라 굳이 안 써도 됨.

struct Plan{
    string name;
    int start;
    int playtime;

    Plan(string a, string b, string c) {
        name = a;
        int time = (ctoi(b[0]) * 10 + ctoi(b[1])) * 60;
        start = time + (ctoi(b[3]) * 10 + ctoi(b[4]));
        playtime = stoi(c);
    }

    Plan(string a, int b, int c) {
        name = a;
        start = b;
        playtime = c;
    }

    int ctoi(char c) {
        return c - '0';
    }

    // 작은 수부터 (부호가 함수명과 반대임을 기억하자)
    bool operator< (const Plan &other) const {
        return start > other.start;
    }
};

3. 로직

우선순위 큐(pq)에서 가장 상위 원소(now)를 뺀다.
(아직 pop하지 않고) stack(s)이 비어있지 않다면,
- s의 가장 상위 원소 추출 후 s.pop()
- 현재 시간보다 pq 원소의 시작 시간이 더 크다면,
  - 시간이 남았으므로, pq에 현재 시간과, 남은 소요시간을 넣는다.
  - pq에 넣으면, 방금 넣은 원소가 가장 상위 원소가 된다.
  - 이후 for문은 실행하지 않음.
- 그렇지 않으면, s에 그대로 다시 넣고 이후 진행
```
if(!s.empty()) {
  node = s.top();
  s.pop();

  if(now.start > cur_time){
    pq.push({과목, 시작시간, 남은 소요시간});
    continue;
  }
}
else
  s.push(node);
```
pq.pop()
다음 상위 원소(next)를 뺀다.
현재 시간은 now의 시작시간 + 소요시간
만약 현재 시간이 next의 시작시간보다 작거나 같으면 완료
아니라면, 소요시간만큼 빼서 s에 push

4. 전체 코드

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

using namespace std;
using pii = pair<int, int>;

struct Plan{
    string name;
    int start;
    int playtime;
    
    Plan(string a, string b, string c) {
        name = a;
        int time = (ctoi(b[0]) * 10 + ctoi(b[1])) * 60;
        start = time + (ctoi(b[3]) * 10 + ctoi(b[4]));
        playtime = stoi(c);
    }
    
    Plan(string a, int b, int c) {
        name = a;
        start = b;
        playtime = c;
    }
    
    int ctoi(char c) {
        return c - '0';
    }
    
    bool operator< (const Plan &other) const {
        return start > other.start;
    }
};

vector<string> solution(vector<vector<string>> plans) {
    vector<string> answer;
    priority_queue<Plan> pq;
    stack<Plan> s;
    
    for(auto p : plans)
        pq.push(Plan(p[0], p[1], p[2]));    
    
    int cur_time = 0;
    while(!pq.empty()) {
        Plan now = pq.top();
        
        if(!s.empty()) {
            Plan node = s.top();
            s.pop();
            
            if(now.start > cur_time) {
                pq.push(Plan(node.name, cur_time, node.playtime));
                continue;
            }
            else {
                s.push(node);
            }
        }
        
        pq.pop();
        Plan next = pq.top();
        cur_time = now.start + now.playtime;
        
        if (cur_time <= next.start) {
            answer.push_back(now.name);
        }
        else {
            s.push(Plan(now.name, now.start, now.playtime - (next.start - now.start)));
        }
    }
    
    while(!s.empty()) {
        Plan cur = s.top();
        s.pop();
        
        answer.push_back(cur.name);
    }
    
    return answer;
}

5. 소감

핵심은 스택에 쌓인 처리하지 못한 과목을 어떻게 할지인 것 같다.
사실 원소가 여러 개 담긴 STL의 연산자 오버로딩을 해본 적이 없었는데, 설마 이게 될까? 했는데 됐다.
다른 사람 코드를 참조하니 나랑 비슷하게 작성한 사람이 있었다.
우선순위 큐… 매우 유용하다. 넣으면 정렬이 되어버린다니

Programmers 176962.과제 진행하기

1. 문제설명

2. 알고리즘 설계

3. 로직

4. 전체 코드

5. 소감