|| 문제설명 ||
- 하드디스크는 한 번에 하나의 작업만 수행할 수 있다.
- 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있지만 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것이다.
- 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성하라.(단, 소수점 이하의 수는 버린다.)
- jobs : 각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열
_ jobs의 길이 : 1 이상 500 이하
_ jobs[i] = [작업이 요청되는 시점, 작업의 소요시간]
_ 각 작업에 대해 작업이 요청되는 시간 : 0 이상 1,000 이하
_ 각 작업에 대해 작업의 소요시간 : 1 이상 1,000 이하
_ 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리|| 문제해결과정 ||
- 들어온 순서대로 작업시간이 적은 순부터 처리
- priotiry_queue<int> 생성(오름차순)
- for문|| 코드 ||
[2020.08.09] 실패(segmentation fault)
#include <string>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
// 들어온 순서대로 작업시간이 적은 순부터 처리
using namespace std;
bool compare(const pair<int, int>& a, const pair<int, int>& b) {
return a.second < b.second;
}
int solution(vector<vector<int>> jobs) {
priority_queue<int, vector<int>, greater<int>> pq;
vector<pair<int, int>> tmp;
int answer = 0, time = 0, i = 1, j = 0, size = jobs.size();
while(j < size) {
if(time == 0) {
time = jobs[0][1] - jobs[0][0];
answer += time;
}
else {
for(;jobs[i][0] <= time; i++) {
tmp.push_back({jobs[i][0], jobs[i][1]});
}
sort(tmp.begin(), tmp.end(), compare);
time += tmp.front().second - 1;
answer += time - tmp.front().first;
tmp.erase(tmp.begin());
}
j++;
}
return answer/size;
}
- 2번째 while문에서 core dumped 발생
[문제 요약]
1. 하드디스크는 한 번에 하나의 작업만을 수행하는데 이때 각 작업의 요청부터 종료까지 걸린 시간의 평균이 최소가 되게 하고 그 값을 리턴하라.
2. jobs[i] = {작업이 요청되는 시점, 작업의 소요시간}
3. 하드디스크가 작업을 수행하고 있지 않을 때는 먼저 요청이 들어온 작업부터 처리합니다.
[변수]
- vector<pair<int, int>> q : 요청된 작업들이 대기하는 곳 (알고리즘에 의해 정렬된 상태)
- int i : 다음 작업
- int cur_time : 현재 시간
- bool comp : 정렬의 유/무 → 시간 절약(중복 정렬 제거)
[알고리즘]
- q의 정렬 방법 : 요청된 작업들 중 가장 적은 작업시간을 가진 작업 우선 (먼저 실행된 작업량만큼 기다려야하기 때문)
- 현재시간과 같거나 적으면 대기큐(q)에 들어가 실행을 기다리고
크다면 기존 대기큐(q)에 있는 작업들 중 가장 적은 작업시간을 가진 작업을 실행하고 큐에서 제거
- 디스크가 작업을 수행하고 있지 않을 때는 다음 작업을 수행
[주의사항]
주어진 jobs는 정렬되지 않은 상태일 수도 있기에 스케줄링하기 전에 미리 정렬한 뒤 실행한다.[2021.01.20]
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(pair<int, int> a, pair<int, int> b) {
return a.second > b.second;
}
int solution(vector<vector<int>> jobs) {
int answer = 0, time = 0, i = 0;
bool comp = false;
vector<pair<int, int>> q;
while(i < jobs.size() || !q.empty()) {
if(i < jobs.size() && time >= jobs[i][0]) {
q.push_back({i, jobs[i][1]}); i++;
comp = false;
}
else {
if(!comp) {
sort(q.begin(), q.end(), compare);
comp = true;
}
if(q.empty()) {
time = jobs[i][0];
q.push_back({i, jobs[i][1]}); i++;
}
time += q.back().second;
answer += time - jobs[q.back().first][0];
q.pop_back();
}
}
return answer/jobs.size();
}
[2021.01.20]
1) 주어진 jobs가 정렬이 되지 않은 경우#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(pair<int, int> a, pair<int, int> b) {
return a.second > b.second;
}
int solution(vector<vector<int>> jobs) {
int answer = 0, time = 0, i = 0;
bool comp = false;
vector<pair<int, int>> q;
sort(jobs.begin(), jobs.end());
while(1) {
if(i < jobs.size() && jobs[i][0] <= time) {
q.push_back({jobs[i][0], jobs[i][1]});
i++; comp = true;
}
else {
if(i < jobs.size() && q.empty()) {
q.push_back({jobs[i][0], jobs[i][1]});
time = jobs[i][0];
i++;
}
else {
if(comp) {sort(q.begin(), q.end(), compare); comp = false;}
time += q.back().second;
answer += time - q.back().first;
q.pop_back();
}
}
if(i == jobs.size() && q.empty()) break;
}
return answer/jobs.size();
}
코드 정리
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(vector<int> a, vector<int> b) {
return a[1] > b[1];
}
int solution(vector<vector<int>> jobs) {
int answer = 0, cur_time = 0, i = 0;
bool comp = false;
vector<vector<int>> q;
sort(jobs.begin(), jobs.end());
while(i < jobs.size() || !q.empty()) {
if(i < jobs.size() && jobs[i][0] <= cur_time) {
q.push_back(jobs[i++]);
comp = true;
continue;
}
if(q.empty()) {
cur_time = jobs[i][0];
q.push_back(jobs[i++]); // 정렬 횟수 줄이기
}
else {
if(comp) {
sort(q.begin(), q.end(), compare);
comp = false;
}
cur_time += q.back()[1];
answer += cur_time - q.back()[0];
q.pop_back();
}
}
return answer / jobs.size();
}
Q. 무슨 차이 때문에 다음과 같은 결과가...
바뀐 점
1) continue문
2) while문의 조건
3) q의 타입 : pair<int, int> → vector<vector<int>>
정답 : 3
내 생각에는 정렬할 때 시간이 걸리나...[2021.01.21]
- 우선순위 큐 사용 : priority_queue
- 우선순위 큐를 사용할 때 특정 정렬규칙을 만들기 위해서는 다음의 함수를 만들어줘야한다.struct compare {
bool operator()(pair<int, int>&a, pair<int, int>&b) {}
};#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct compare {
bool operator()(pair<int, int>&a, pair<int, int>&b) {
return a.second > b.second;
}
};
int solution(vector<vector<int>> jobs) {
int answer = 0, cur_time = 0, i = 0;
bool comp = false;
priority_queue<pair<int, int>, vector<pair<int, int>>, compare> q;
sort(jobs.begin(), jobs.end());
while(i < jobs.size() || !q.empty()) {
if(i < jobs.size() && jobs[i][0] <= cur_time) {
q.push({jobs[i][0], jobs[i][1]});
i++;
continue;
}
if(q.empty()) cur_time = jobs[i][0];
else {
cur_time += q.top().second;
answer += cur_time - q.top().first;
q.pop();
}
}
return answer / jobs.size();
}
