지난 토요일 폭풍같은 후회와 함께 라인 코테를 치르고,,
어려울거라 생각했는데, 막상 어렵다기 보단 시간이 많이 부족해서 연습량 부족을 뼈저리게 느끼며 시험을 치뤘다,,
후회는 주말까지 하고 오늘부턴 또 새로 준비를 시작해야징
새로운 코테가 2주도 안남았는데, c++ 이 옵션에 없다...! swift로 급하게 연습해야징ㅜ
Programmers [힙] 디스크 컨트롤러
문제 목표
작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return
입출력 예
제한 사항
나의 풀이
컨트롤러는 한번에 하나의 작업만 수행할 수 있고, 각기 다른 수행시간과 요청 시간을 가진 작업들의 '요청-완료' 시간들의 평균을 최소화 하는 방법을 찾는 문제.
처음에 최소화하는 방향을 잡지 못해 주어진 예제로 모든 경우의 수를 다 따져보았다.
하지만 명확한 기준을 잡기 어려웠고, 문제 자체가 [힙] 카테고리에 있었기에 우선순위 큐를 사용하는 듯 하였는데,
'그렇다면 단순히 실행 시간이 짧은 or 긴 순서대로 수행해야 한다고? 그렇게 단순하다고?' 잘 이해가 되지 않았다,,
이리 저리 고민을 해보다가 함께 공부하는 친구의 블로그에 혹시나 들어가 봤더니 친구 역시 이 문제에 대한 풀이를 기록해 두었길래 확인해봤다
예상한대로 우선순위 큐를 사용해 실행 시간이 짧은 것 부터 처리 해 주었어야 했는데, 친구에게 연락까지 해서 물어보고 고민했다!
고민한 결과,
'요청 - 완료 시간 = 대기시간 + 실행 시간' 이므로 이 중 실행 시간은 이미 결정 되었기에 대기시간을 줄이는 것이 관건이고
이는 곧 실행시간이 짧은 것 부터 실행하는 것이 대기시간을 최대한 줄이는 방법임을 의미한다.
#include <vector>
#include <queue>
#include <algorithm>
// 프로그래머스 힙 - Level3 디스크 컨트롤러, 맞음!!! 하ㅜ 연습 좀 해라,,
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, sec = 0;
int nextTurn = 1;
pair<int, int> nowTask;
priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;
sort(jobs.begin(), jobs.end()); // jobs 요청된 시간 순으로 정렬
pq.push(make_pair(jobs[0][0], jobs[0][1]));
while(!pq.empty()) {
nowTask = pq.top();
pq.pop();
if(sec < nowTask.first){
sec = nowTask.first;
}
sec += nowTask.second;
answer += sec - nowTask.first;
for (int i = nextTurn; i < jobs.size() ; ++i) {
if(jobs[i][0] <= sec){
pq.push(make_pair(jobs[i][0], jobs[i][1]));
nextTurn++;
}else{
break;
}
}
if(pq.empty() && nextTurn<jobs.size()){
pq.push(make_pair(jobs[nextTurn][0], jobs[nextTurn][1]));
nextTurn++;
}
}
return answer / jobs.size();
}매 초를 count 하며 관리하고, 해당 시점에 요청 되어 있는 것이 있다면 우선순위 큐를 이용하여 실행시간이 짧은 것 부터 실행시킨다.
요청되어 있는 것이 없다면 그 이후 가장 빨리 요청되는 시점으로 시간을 조절하고, 모든 작업이 수행될 때 까지 수행하며 요청부터 실행 완료까지의 시간을 합해 작업의 수로 나누어 반환하였다.
다른 풀이
이분의 풀이는 가장 실행 시간이 짧은 순으로 task들을 정렬하고, 정렬한 배열을 반복적으로 탐색하며 현재 시간보다 이전에 들어온 것들이면 처리하는 방식이다.
코드 상으로는 나보다 훨씬 간단해보이긴 하는데, 흠 while 문 안에서 반복적으로 for문이 실행되는 부분이 항상 좋을지는,, 잘 모르겠당
