문제
https://programmers.co.kr/learn/courses/30/lessons/42627
풀이
풀이는 생각보다 간단한데, 평균이 최소가 되려면 해당 시간에 가능한 작업 중에서 가장 짧은 시간이 걸리는 작업을 수행해야 한다. 이유는 수학적인 증명은 안했지만, 가장 빨리 끝나는 것을 해야 다른 작업이 질질 끌리는 것을 막을 수 있기 때문이다.
예를 들어 0초에 작업이 1, 2, 3, 4가 걸리는게 4개가 들어온다고 했을때, 가장 짧은 것을 빨리 마치고 다음 짧은 것을 해치워야 작업중 다른 시간이 늘어나는 속도가 최소가 된다. 증가하는 속도는 1 * (밀려있는 작업 수) 인데 이 밀려있는 작업 수를 최대한 빨리 줄이는 방법이 가장 빨리 끝나는 작업을 먼저 해치우는 것이다.
따라서 구현 같은 경우에는 작업이 들어오는 시간을 기점으로 오름차순으로 compare 함수를 사용해서 정렬하고 (따로 compare 함수를 사용하지 않아도 알아서 first나 0번째 값을 사용한다고 한다. 추후에 알아보기) 정렬된 벡터를 가지고 현재 시간에 가능한 작업을 힙에 넣고 -> 힙에서 top을 꺼내고 -> 해당하는 시간만큼 더하고 -> 그 다음 힙에 가능한 작업을 넣고를 반복했다. 만약에 가능한 작업이 없다면 가장 빨리 들어올 작업때의 시간으로 한번에 앞당기고, 이미 끝난 작업은 매크로 변수를 사용해서 무시했다. 다만 중복을 계속 검사하기 때문에 삭제하는게 더 효율적일 수 있다. 다음에 확인해보자.
참고로 구조체로 정의한 cmp 같은 경우에는 sort의 compare와 비교 연산자를 반대로 정의해야 제대로 돌아간다고 한다. 이 점을 주의하자.
실수?
- STL 사용 미숙
- 중복을 검사하는 코드를 없앨 순 없을까?
- compare와 cmp는 정렬하는 방향이 같다. 주의하자.
코드
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#define done 99999
using namespace std;
struct cmp{
bool operator()(vector<int> front, vector<int> back){
return front[1] > back[1];
}
};
bool compare(vector<int> front, vector<int> back){
return front[0] < back[0];
}
int solution(vector<vector<int>> jobs) {
int answer = 0;
int time = 0;
priority_queue <vector<int>, vector<vector<int>>, cmp> pq;
sort(jobs.begin(), jobs.end(), compare);
for(;;){
int min_time = done; // 가장 작은 시간을 저장
for(int i = 0; i < jobs.size(); i++){
if(jobs[i][0] != done && jobs[i][0] <= time) {
pq.push(jobs[i]);
jobs[i][0] = done;
jobs[i][1] = done;
}
if(jobs[i][0] != done && min_time > jobs[i][0]) {
min_time = jobs[i][0];
}
}
if(min_time == done && pq.size() == 0){
break;
}
if(pq.size() == 0){
time = min_time;
}
else {
printf("%d ", pq.top()[1]);
answer += time - pq.top()[0] + pq.top()[1];
time += pq.top()[1];
pq.pop();
}
printf("%d \n", time);
}
return answer / jobs.size();
}
