[고득점Kit][힙] 디스크 컨트롤러 ⭐⭐⭐

C++로 풀이했습니다.
출처 : 프로그래머스 고득점 Kit 문제 풀이. https://programmers.co.kr/learn/challenges

[힙] 디스크 컨트롤러

난이도 ⭐⭐⭐

문제

풀이

틀린 내 풀이

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>

using namespace std;

struct compare_queue
{
   bool operator() (vector<int> a, vector<int> b)
   {
      return a[1] - a[0] > b[1] - b[0];
   }
};

bool compare_sort(vector<int> a, vector<int> b)
{
   if (a[0] == b[0])
      return a[1] < b[1];
   return a[0] < b[0];
}

int solution(vector<vector<int>> jobs) {
   int answer = 0;

   priority_queue<int> q_sum;
   priority_queue<vector<int>, vector<vector<int>>, compare_queue> waiting;

   int total_time = 0;
   for (int i = 0; i < jobs.size(); i++)
   {
      total_time += jobs[i][1];
   }

   sort(jobs.begin(), jobs.end(), compare_sort);

   int index = 0;   // jobs 순회
   int endTime = 0;
   bool processing = false;
   for (int time = 0; time < total_time; time++)
   {
      while (true)
      {
         if (time == jobs[index][0])
         {
            waiting.push(jobs[index]);
            index++;
         }
         else
            break;
      }

      if (!processing)
      {
         endTime = time + waiting.top()[1];
         waiting.pop();
         processing = true;
      }
      else if (time == endTime)
      {
         processing = false;
         endTime = 0;
      }
   }

   return answer;
}

위 코드는 제 틀린 풀이입니다 😥 (+ answer에 합산하는 부분은 구현 안했던 상태)

통과됐던 풀이

위 풀이로 계속해서 난관에 부딪쳤기 때문에 구글링으로 다른 분들의 풀이를 참고하였다.

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>

using namespace std;

struct compare_queue
{
	bool operator() (vector<int> a, vector<int> b)
	{
		return a[1] > b[1];
	}
};

bool compare_sort(vector<int> a, vector<int> b)
{
	if (a[0] == b[0])
		return a[1] < b[1];
	return a[0] < b[0];
}

int solution(vector<vector<int>> jobs) {
	int answer = 0;

	priority_queue<vector<int>, vector<vector<int>>, compare_queue> waiting;  // 우선순위 큐 (jobs로부터 현재 시점time에서 실행 가능한 작업들만 모아둔 큐. 평균이 작아지는 방향으로 우선순위가 부여 됨.)

	sort(jobs.begin(), jobs.end(), compare_sort);

	int index = 0; // jobs 순회 인덱스
    int time = 0; // ✨현재 시간✨
    while (index < jobs.size() || !waiting.empty())
    {
        if (index < jobs.size() && jobs[index][0] <= time) // jobs에서 가져올게 남아있고 ✨요청시간이 현재 time보다 작을때만✨ 우선순위 큐로 가져올 수 있음
        {
            waiting.push(jobs[index]); // 우선순위 큐에 추가
            index++; 
            continue; // jobs[index][0] <= time을 만족하는 원소는 다 받도록 while문, if문 조건 다시 반복
        }
        
        if (!waiting.empty()) // 큐가 비어있지 않다면, 즉 디스크가 일하는 동한 현재 시점 전에 jobs로부터 들어온 것들이 있었다면
        {
            time += waiting.top()[1];  // 요청시간(else) + 소요시간 = 끝나는 시간 
            answer += time - waiting.top()[0];  // answer += 현재 시간 - 요청시간
            waiting.pop();
        }
        else // 우선순위 큐는 비었는데 jobs에서 가져올 것은 남아있는 경우
        {
            time = jobs[index][0];  // 현재시간 time을 jobs내의 ✨제일 빨리 들어오는 작업 시간✨(jobs가 정렬되있어서 가능한 일)으로 초기화해놓기 (필요없는 연산 방지)
        }
    }

	return answer / jobs.size();
}

비교, 오답 정리

• 우선 순위큐 자료 구조 활용
  • 실행할 수 있는 작업들 중에서 요청시간부터 종료시점까지 걸리는 시간의 평균이 작아지는 방향으로 우선순위를 두어 다음 실행할 작업을 선택할 수 있는 우선순위 큐를 사용한다.
    • ⭐모든 해를 다 구한후 그중에서 가장 평균이 작은 최적해를 뽑는 풀이는 안된다.
      • 디스크 입장에선 다음에 어떤 작업이 들어올지 알 수 없기 때문이다.
      • 그때 그때 작업할 수 있는 것들 중에서 평균이 작아지는 방향으로 선택해 나가야함
    • 틀렸던 부분
      • 👉 a[1] - a[0] > b[1] - b[0]
        • 평균이 작아지는 방향으로 작업을 선택하기 위해 우선 순위 큐의 우선 순위를 정해줄 때 이렇게 하면 틀리더라 ㅠ ㅠ
        • 각각의 케이스들의 작업의 요청부터 종료까지 걸린 시간 차이는 딱 저 값으로 나던데.. 사실 아직도 이해가 잘 안된다. 이게 왜 틀린지는 따흑..
      • 👉 a[1] > b[1]
        • 정답은 요것 ! 그냥 처리시간이 가장 적은 작업부터 처리하면 요청부터 종료까지의 평균 시간이 줄어들 수 있다.
• jobs 가 정렬되어 있는건 아니기 때문에 요청 시간을 기준으로 오름 차순 정렬이 되어야 평균을 좀 더 쉽게 구할 수 있다.
  • jobs를 요청 시간 오름차순으로 정렬하면 현재시간 time을 jobs[index][0]로 초기화하면 다음 요청시간 들 중 가장 빠른 시간으로 초기화 된다는것이 보장 된다.
  • bool compare_sort(vector<int> a, vector<int> b)
• 원소는 vector<int>이며 vector<vector<int>>타입의 벡터 위에서 우선순위 큐를 돌릴 것. 그냥 평소처럼 vector<int>만 써줘가지고 에러에 부딪쳤었다..😭

  priority_queue<vector<int>, vector<vector<int>>, compare_queue> waiting;
  

• 나는 for문을 두어 라면공장 문제처럼 time을 1씩 증가시키는 방식으로 반복하려 했으나 이러니까 작업이 끝나자마자 해당 time에 또 새로운 작업이 바로 시작되는 것을 구현하는게 좀 어려웠다 ㅠ
  • 우선순위큐가 비거나 혹은 jobs가 빌 때 까지만 while문으로 반복문을 돌리면 된다.
• 이해하는데 도움이 많이 되었던 블로그

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기