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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42627

코딩테스트 연습 - 디스크 컨트롤러

문제 요약

 

1. vector안에 [업무시간, 업무 요청시간]의 배열들이 저장되어있다.

2. 각 업무의 요청부터 종료시간까지 걸린 시간의 평균이 가장 작은 값을 구하라.

예시로 아래와 같은 값들이 들어올 경우, 아래 사진으로 값을 구하면 평균 시간이 더 작은 결과가 나온다.

 

 

 

핵심 포인트

 

각 작업의 요청부터 종료까지 걸리는 평균 시간을 단축하기 위해, 어떤 업무를 시작하는지 그 기준은 다음과 같습니다.

 

1. 업무 요청 시간이 빠름
2. 업무 시간(=업무를 하는데 걸리는 시간)이 빠름

 

만약 업무 시간이 동일할 경우, 업무 요청 시간이 더 빠른 것을 선택하는 것이 이득입니다.

두 가지 요소를 작은 값 순으로 동시에 정렬하는 것은 오히려 복잡할 수 있으므로, timer라는 시간 변수를 별도로 설정하여

업무 시간이 빠르면서 동시에 업무 요청 시간이 빠른 대상을 선택해야 합니다.

 

문제 풀이

 

1. 변수를 선언합니다. 각 변수의 의미는 다음과 같습니다.

int answer = 0, timer = 0, cnt = jobs.size();

(1) answer = 각 작업의 요청부터 종료까지 걸리는 시간
(2) timer = 시간. +1씩 증가합니다.

(3) cnt = 작업의 갯수

 

2. jobs를 다음과 같이 정렬합니다. comp 정렬의 뜻은 다음과 같습니다.

bool comp(const vector<int> &a, const vector<int> &b){
    return a[1] <= b[1];
}

int solution(vector<vector<int>> jobs) {
    int answer = 0, timer = 0, cnt = jobs.size();
    sort(jobs.begin(), jobs.end(), comp); // {요청시간, 업무시간} // 단, 업무시간이 짧은 순으로 배치
    ...

comp를 통해 jobs[i][1]의 값이 더 작은 순으로 정렬됩니다. 즉, 업무 시간(=업무를 하는데 걸리는 시간)이 더 빠른 순으로 정렬됩니다.

 

3. 다음은 while문입니다.

    while(!jobs.empty()){
        for(int i=0; i<jobs.size(); i++){ // 1
            if(jobs[i][0]<=timer){ // 2
                timer += jobs[i][1]; // 3
                answer += (timer-jobs[i][0]); // 4 
                jobs.erase(jobs.begin()+i); // 5
                break;
            }
            if(i==jobs.size()-1) timer++; // 6
        }
    }

(1) jobs의 사이즈만큼 for문을 돌립니다.

(2) 만약 jobs[i][0](=업무 요청 시간)이 timer 이하일 경우...

->(3) timer에 해당 업무 시간(=업무를 진행하는데 걸리는 시간)을 추가합니다.

->(4) answer에는 timer - 업무 요청시간을 추가합니다. 이로써 해당 업무의 요청 시간부터 업무 종료 시간까지가 더해집니다.

->(5) 해당 위치의 업무를 벡터에서 제거합니다.

(6) 만약 jobs.size()-1까지 갔는데도 (2)번에 해당되는 값이 존재하지 않을 경우, timer을 +1 합니다.

 

4. 정답을 다음과 같이 반환합니다.

 return answer/cnt; // (각 업무들의 요청시간부터 종료시간까지의 합 / 전체 업무 갯수)

 

 

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

using namespace std;

bool comp(const vector<int> &a, const vector<int> &b){
    return a[1] <= b[1];
}

int solution(vector<vector<int>> jobs) {
    int answer = 0, timer = 0, cnt = jobs.size();
    sort(jobs.begin(), jobs.end(), comp); // {요청시간, 업무시간} // 단, 업무시간이 짧은 순으로 배치
    while(!jobs.empty()){
        for(int i=0; i<jobs.size(); i++){
            if(jobs[i][0]<=timer){
                timer += jobs[i][1];
                answer += (timer-jobs[i][0]);
                jobs.erase(jobs.begin()+i);
                break;
            }
            if(i==jobs.size()-1) timer++;
        }
    }
    return answer/cnt;
}