[힙] 프로그래머스 42627: 디스크 컨트롤러
// 2021-03-13 18:12 시작
// https://programmers.co.kr/learn/courses/30/lessons/42627
// 디스크 컨트롤러
// 2021-03-13 18:56 종료
// correct: 42627
/*아이디어 ~18:35까지 생각함
벡터를 첫번째 값(요청시간) 기준으로 정렬하고 시작한다.
priority_queue. pair의 소요시간 기준으로 작은 것이 우선순위가 크게 정렬
1. 두 번째 값이 작으면 우선순위가 높다
2. 두 번쨰 값이 같은 경우, 요청시간이 작은 것이 우선순위가 높다.
=> pair의 크기 비교에 따라, greater<pair<int, int>>로 하고 소요시간을 처음 인자, 요청시간을 두번째 인자로 둔다.
벡터 끝까지 훑을 때까지 time++을 반복한다. : 이터레이터로 진행
while 이터레이터가 end()가 아니면
1. work가 진행중이면 work를 하고 time++
2. work==0인 상태이면
1) 벡터[0]이 time과 같아지는 순간까지 벡터를 훑고 큐에 추가
2) queue 확인하고 안 비었으면 다음 work 채택
answer += time-요청시점
3) queue가 비었으면 time++
3. answer /= 벡터.size();
=> 03.17 개선: time 계산을 좀 더 빠르게 진행
while 이터레이터가 end()가 아님, 또는 q가 비어있지 않다면
1) 벡터[0]이 time과 같아지는 순간까지 벡터를 훑고 큐에 추가
2) queue 확인하고 안 비었으면 다음 work 채택
answer += time-요청시점 + 소요시간(work)
time +=work
3) queue가 비었으면 time = 다음 job의 도착시간
[시간복잡도]
안쪽 while문: 총 n번 수행 (모든 job을 큐에 넣어야 함)
바깥쪽 while문: 총 n번 수행 (모든 job을 수행해야함)
큐에 삽입/삭제: 한번에 logN인데 이런 연산을 n번함 => 2nlogn (2는 삽입도 하고 삭제도 하기 때문)
//else: O(디스크가 놀고 있는 시간)
//결론: 2nlogn +디스크가 놀고 있는 시간=> O(디스크가 놀고 있는 시간+nlogn)
결론: O(nlogn)
[실수]
// 실수: 추가조건- iter != end()
// iter가 end까지 갔는데 (*iter[0]을 계속 호출해서 세그멘테이션 폴트남)
// 실수: iter!=jobs.end() 조건을 뒤에 줬더니 (*iter) 연산을 먼저 해서 세그멘테이션 폴트
[검색(내가 잘 몰랐던 부분)]
- 2차원 벡터 정렬 https://hanyeop.tistory.com/67
- pair의 크기 비교 https://m.blog.naver.com/PostView.nhn?blogId=kks227&logNo=220172825836&proxyReferer=https:%2F%2Fwww.google.com%2F
- 벡터 이터레이터 만드는 방법 https://hyeonstorage.tistory.com/318
- make_pair, pair.first https://blockdmask.tistory.com/64
- pair는 <utility>에 존재
*/
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility> // pair
using namespace std;
int solution(vector<vector<int>> jobs) {
int answer = 0;
// 벡터를 첫번째 값(요청시간) 기준으로 정렬하고 시작한다.
sort(jobs.begin(), jobs.end());
// priority_queue. pair의 소요시간 기준으로 작은 것이 우선순위가 크게 정렬
// 1. 두 번째 값이 작으면 우선순위가 높다
// 2. 두 번쨰 값이 같은 경우, 요청시간이 작은 것이 우선순위가 높다.
// => pair의 크기 비교에 따라, greater<pair<int, int>>로 하고 소요시간을 처음 인자, 요청시간을 두번째 인자로 둔다.
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
// 벡터 끝까지 훑을 때까지 time++을 반복한다. : 이터레이터로 진행
vector<vector<int>>::iterator iter = jobs.begin();
int time = 0, work = 0;
// while 이터레이터가 end()가 아니면
// 또는 큐에 뭔가 있으면
// 바깥while
while(iter!=jobs.end() || !pq.empty())
{
// // 1. work가 진행중이면 work를 하고 time++
// if (work>0)
// {
// work--;
// time++;
// }
// // 2. work==0인 상태이면
// else
// {
// 21.03.17 개선사항
// work를 받자마자 수행하는 과정을 추가하여 윗 부분의 if~else를 날려버리자
// 1) 벡터[0]이 time과 같아지는 순간까지 벡터를 훑고 큐에 추가
// 실수: 추가조건- iter != end()
// iter가 end까지 갔는데 (*iter[0]을 계속 호출해서 세그멘테이션 폴트남)
// 실수: iter!=jobs.end() 조건을 뒤에 줬더니 (*iter) 연산을 먼저 해서 세그멘테이션 폴트
// a: 이번 while문에서 q에 들어가는 job의 개수
//log(a!) -> nlog(n)
while (iter != jobs.end() && (*iter)[0] <= time)
{
// 소요시간, 도착시간
pq.push(make_pair((*iter)[1], (*iter)[0]));
iter++;
}
// 2) queue 확인하고 안 비었으면 다음 work 채택
if (!pq.empty())
{
work = pq.top().first;
// answer += time-요청시점+ 수행시간
answer += time-pq.top().second+ work;
pq.pop(); // log(a)
time += work;
}
// 3) queue가 비었으면 time++
else
{
// time++;
// 21.03.17 개선사항
// 도착시간 순으로 jobs가 정렬되어 있으므로
// 바로 다음 job의 도착시간으로 jump
time += ((*iter)[0]-time);
}
// }
}
// 3. answer /= 벡터.size();
answer /= jobs.size();
return answer;
}
Author And Source
이 문제에 관하여([힙] 프로그래머스 42627: 디스크 컨트롤러), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ember/힙-프로그래머스-42627-디스크-컨트롤러저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)