[프로그래머스] 디스크 컨트롤러 (C++)

📌 참고

교공 알고리즘 스터디에서 다룬 문제는 19주차부터 벨로그에 기록하고 있습니다 (18주차 이전 문제들을 추후 복습 겸 업로드할 계획도 있습니다 🤗) 그 외 개인적으로 풀어본 백준 및 프로그래머스 문제는 스스로 유의미하다고 여겨진 부분들이 있는 문제만 선별하여 벨로그에 기록하고 있습니다 벨로그에 올라오지 않은 다른 문제와 코드가 궁금하신 분들은 아래의 github에서 추가로 확인하실 수 있습니다 👀 방문해주셔서 감사합니다 🙏

💚 github | dianstar/Algorithm-BOJ
💚 github | dianestar/Algorithm-Programmers

코딩테스트 고득점 Kit > 힙(Heap)

디스크 컨트롤러 | 문제 바로가기

문제풀이 (2022-02-23 WED 💻)

🤔 사담

스스로 테스트케이스를 생각해내기가 너무 어렵다
입출력 예제를 적게 주는 프로그래머스는 당연하고
백준도 예제가 하나면 일단 긴장부터 하게된다..😥
경우의 수랑 복잡도 미리 잘 따져보고
문제를 사전에 설계해서 푸는 것의 중요함을 깨닫는 중..
그래서 오늘은 예외 테케를 뽑아낼 수 있는 핵심 위주 로 정리해보고자 한다

⭐ 풀이의 핵심

오랜만에 priority_queue를 활용하는 문제였다

• 기본적으로는 요청 시점이 빠른 순으로 정렬
  👉 ex) jobs {{2,6}, {0,3}, {1,9}} 와 같이 jobs가 반드시 정렬되어 주어진다는 보장이 없음
• 현재 시점을 저장하는 변수 (아래 코드에서 currTime) 선언해서 요청 시점과 비교
  • 현재 시점 이전에 요청이 도착한 작업이 여러 개일 경우
    해당 작업들에 대해 소요시간이 적은 순으로 priority_queue에 push
    👉 주어진 테케 jobs {{0,3}, {1,9}, {2,6}} 에서도 확인 가능한 조건
    👉 ex) jobs {{0,3}, {0,5}, {0,8}}
  • 현재 시점에 들어온 요청이 없어 하드디스크기 쉬는 시간은 answer에 포함하지 않도록
    pq가 비어있을 경우 다음 요청이 들어오는 시점으로 현재 시점을 업데이트
    👉 ex) jobs {{1,2}, {1,3}, {8,6}}와 같이 작업들 간의 공백 시간이 생길 수 있음

이 정도가 핵심 조건이자 흐름이었던 것 같다

🚨 간과 또는 실수한 부분

처음에는 jobs 벡터에서 값을 빼내면서
obs 벡터가 empty가 될 때까지 반복하는 식으로 구현하려 했는데
시간초과 를 유발하기 딱 좋은 코드였다
jobs의 인덱스를 가리키는 변수 (아래 코드에서 i) 를 옮겨가며
i가 jobs의 사이즈 범위 밖으로 벗어나기 전까지 반복하는 방식이 보다 효율적이고 현명했다

priority_queue 비교 연산자 오버로딩 부분에서 부등호 방향을 잘못 넣어줘서
답이 이상하게 나왔었다
매번 algorithm 헤더의 sort 함수에서의 방식이랑 헷갈렸는데
이번 기회에 아래 정리를 해보았다 👇

➕ 참고 priority_queue 비교연산자

• priority_queue(자료형, 구현체, 비교연산자) 비교연산자 부분에 cmp 구조체를 선언해서 연산자 오버라이딩을 해준다 (cmp 구조체 대신 greater<자료형>, less<자료형> 도 사용 가능)
• 부등호에 주의한다! (아래 예시 코드 및 설명 참조)

// sort
bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
	return a.second < b.second; // 오름차순
}

// priority_queue
struct cmp {
	bool operator()(const pair<int,int> &a, const pair<int,int> &b) {
    	return a > b; // 오름차순
    }
};

이와 같이 부등호가 반대 방향으로 나타나는 이유는
priority_queue에서 두 값을 비교할 때는
SWAP을 할 것인지 말 것인지를 결정하는 것이 핵심이기 때문!
priority_queue에 새로운 데이터가 들어오면
해당 데이터(자식 노드)를 부모 노드와 비교하여 swap 여부를 결정한다

위의 예시에서 a는 부모 노드, b는 자식 노드를 가리키며
부모 노드(a)가 자식 노드(b) 보다 크다면 true를 return 하고
즉, swap을 하기로 결정하는 것이므로
return a>b가 오름차순으로 정렬할 것을 의미하게 된다

🔽 코드 (C++)

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

using namespace std;

struct cmp {
    bool operator()(const pair<int,int> &a, const pair<int,int> &b) {
        return a.second > b.second;
    }
};

int solution(vector<vector<int>> jobs) {
    // cf) jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간]
    int answer = 0;

    // jobs를 작업 요청 시점이 빠른 순으로 정렬
    sort(jobs.begin(), jobs.end()); 
    // 작업 소요시간이 적은 순으로 저장되는 priority_queue 선언
    priority_queue<pair<int, int>, vector<pair<int,int>>, cmp> pq; 
    int currTime = 0;
    int i = 0;
    int jobsSize = jobs.size();
    while (true) {
        if (i >= jobsSize && pq.empty()) {
            // 모든 작업 처리 완료 시 종료
            break;
        }

        while (i < jobsSize && jobs[i][0] <= currTime) {
            // 현재 시점보다 요청 시점이 빨라 소요시간 기준으로 재정렬이 필요한 작업들을 pq에 push
            pq.push({jobs[i][0], jobs[i][1]});
            i++;
        }
        if (!pq.empty()) {
            // pq가 비어있지 않을 경우
            // pq의 top에 해당하는 작업을 먼저 처리
            answer += (currTime - pq.top().first + pq.top().second);
            currTime += pq.top().second;
            pq.pop();
        }
        else {
            // pq가 비어있을 경우, 즉 현재 시점에 요청된 작업이 없을 경우
            // 다음 요청이 들어오는 시점으로 현재 시점 업데이트
            currTime = jobs[i][0];
        }
    } 
    answer /= jobsSize;

    return answer;
}