[C++] 디스크 컨트롤러

https://school.programmers.co.kr/learn/courses/30/lessons/42627

프로그래머스

 

문제

 

 

 

 

아이디어

 

우선순위 큐를 이용한 스케줄링 문제입니다.

큰 아이디어는 이렇습니다.

 

1) 작업의 길이가 짧은 것을 먼저 해야한다.

2) 1)을 만족해도 요청되는 작업만 수행해야한다.

 

즉, 이 2가지를 고려해서 해결해야합니다.

 

 

풀이이

 

먼저 1) 이전에 2를 해결하기 위해

jobs를 실행시간 기준으로 오름차순 정렬해줍니다.

 

 

그러면 일단 2)를 해결했고,

다음은 1)을 해결해야하는데

 

현재 jobs 배열속에는 시작시간 기준으로만 정렬되어있고

소요시간은 뒤죽박죽합니다.

 

그래서 이 경우에는 우선순위큐를 선언해서

jobs를 하나씩 처리하면 됩니다.

 

 

소요시간기준 최소힙 우선순위큐를 선언하고,

 

index는 jobs를 순회할 색인

currentTime은 총 소요시간입니다.

 

 

메인 로직의 과정은 이렇습니다.

 

1) 현재 걸린 시간보다 작은 작업들은 모두 pq에 밀어넣는다.

pq의 top에는 현재 실행할 수 있는 작업들 중

소요시간이 최소가 되는 작업이 올라와있습니다.

 

2) 큐 Top에 있는걸 빼서 CurrentTime와 answer을 업데이트 한다.

만약 큐에 요소기 없다면, 해당 시간에 수행할 수 있는 일이 없다는 의미이기에

currentTime을 다음 작업 시작시간으로 옮깁니다.

 

3) 답이 나온다.

 

 

힙 문제를 많이 안풀어보다 보니

좀 헤맸습니다.

 

코딩 테이트에서 자주 볼 수 있는 소재이기에,

좀 더 연습할 필요가 있는 것 같습니다.