프로그래머스_디스크 컨트롤러

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

코딩테스트 연습 - 디스크 컨트롤러 | 프로그래머스

처음 문제를 처리할 때는 작업을 처리하고 작업이 끝나는 시점까지 넣을 수 있는 작업들을 다시 스케쥴러에 전부 넣고 그 다음에 고려하는 방식으로 문제를 풀었다. 그래서 다음의 코드를 구현했는데, 70점을 맞았다.

 

리뷰하는 과정에서 문제의 조건에서 작업을 하고 있지 않을 경우 요청 순으로 처리한다는 조건이 있었다.

그래서 작업을 처리하고 있지 않을 때, 스케쥴러에 할 수 있는 작업이 있다면 우선순위에 맞게 처리해야 했다.

여기서, 만약 작업을 처리하고 있지 않는 상황에서, 스케줄러가 비어있는 상황에서의 코드 구현이 틀렸었다.

직관적으로 구현하려고 하니, 자꾸 코드가 복잡해지고 정리가 잘 안됐었다. 그 결과물은 다음과 같다.

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;

// 비교 함수
bool compare(vector<int> v1, vector<int> v2){
    return v1[0]<v2[0];
}
// 작업 시간 짧은 순
struct cmp{
    bool operator()(vector<int> v1, vector<int> v2) {
        return v1[1]>v2[1];
    }
};

void print(priority_queue<vector<int>, vector<vector<int>>, cmp> q){
    while(!q.empty()){
        vector<int> temp = q.top();
        cout<< temp[0] << " "<< temp[1]<<"\n";
        q.pop();
    }
}
int solution(vector<vector<int>> jobs) {
    int answer = 0;
    sort(jobs.begin(), jobs.end(), compare); // 요청 시점 순 정렬
    priority_queue<vector<int>, vector<vector<int>>, cmp> pq;
    
    // 해당 초에 맞게 priority queue에 넣은 후
    // 우선순위에 따라 작업
    vector<bool> check(jobs.size(), false);
    int idx=0, now = 0, total = 0, cnt = 0;
    now = jobs[0][0]; // 맨 처음 요청 시작 시간
    total += now;
    while(cnt < jobs.size()){
        
        // 가능한 것들 q에 추가
        for(int i=0;i<jobs.size();i++){
            // 안 넣었고 시간 가능
            if(check[i] == false && now >= jobs[i][0]){
                pq.push(jobs[i]); // 추가
                check[i]=true; // 표시
            }
        }
        // 하나도 안들어왔으면 가장 빨리 끝날 수 있는 작업 추가
        if(pq.empty()){
            int min_idx = -1, min_time;
            for(int i=0;i<jobs.size();i++){
                // 가지 않은 곳이 있다면
                if(check[i]==false){
                    // 초기화
                    if(min_idx == -1){
                        min_time = jobs[i][0] + jobs[i][1] - now;
                        min_idx = i;
                    }
                    
                    // 가장 짧은 시간
                    else
                        if(min_time > jobs[i][0] + jobs[i][1] - now ){
                            min_time = jobs[i][0] - jobs[i][1] - now;
                            min_idx = i;
                        }
                }
            }
            pq.push(jobs[min_idx]); // 추가
            check[min_idx] = true; // 표시
            now = jobs[min_idx][0]; // 현재 시간 변경
        }
    
        // 한 개 작업 처리
        vector<int> temp = pq.top(); 
        total += (now + temp[1] - temp[0]); // 대기시간 더하기
        now += temp[1]; // 작업시간 더하기 
        pq.pop();
        cnt++;
    }
    
    return total/jobs.size();
}

그래서 다른 사람들의 풀이를 참조하여 만약 스케줄러에서 처리할 작업이 없을 경우를 어떻게 구현할지를 찾아보다가 다음의 블로그 포스팅을 보게 되었다.

https://chaibin0.tistory.com/entry/%EB%94%94%EC%8A%A4%ED%81%AC-%EC%BB%A8%ED%8A%B8%EB%A1%A4%EB%9F%AC

[프로그래머스/알고리즘] 디스크 컨트롤러

핵심은 작업별로 처리한 다음에 시간을 보는 것이 아니라 시간초별로 작업을 처리하는 방식이었다(대박이다..ㅎ).

시간초 별로 스케줄러에 넣을 수 있는 작업들을 넣고 만약 remain(현재 처리중인 작업의 남은 시간)이 0 이하이면 작업을 새로이 처리하는 방식으로 접근한다.

 

시간초 별로 동작하니, 작업이 끝난 상황에서 다시 탐색을 통해서 고려하는 것이 아니라 코드가 간결해졌다.

또한, 시간초가 지나가면서 현재 스케줄러에 처리할 수 있는 작업이 없을 경우에 코드가 이상해지던 문제도 해결할 수 있었다. remain 이 0미만(음수) 일 경우에 계속 작업을 처리하지 않고 그냥 시간만 흐르고 있는 상황이므로 따로 처리를 하지 않아도 됐다. 다만 시간이 지나면서 jobs 배열에 있는 작업을 처리할 수 있는 시간이 되었을 경우 스케줄러에 추가해줄 수 있었다. 이렇게 index들을 전부 스케줄러에 전부 넣어주게 되면 불필요한 연산을 다시 수행할 필요 없이 넘어가면 되었다. 

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;

// 작업 시간 짧은 순 정렬
struct cmp {
	bool operator()(vector<int> v1, vector<int> v2) {
		return v1[1] > v2[1];
	}
};

// 요청 순 정렬
bool compare(vector<int> v1, vector<int> v2) {
	return v1[0] < v2[0];
}

int solution(vector<vector<int>> jobs) {
	sort(jobs.begin(), jobs.end(), compare); // 요청 순 정렬
	priority_queue<int, vector<vector<int>>, cmp> pq;
    
    // 변수 선언
	vector<int> temp;
	int total = 0, idx = 0, now_time = 0, remain = 0;			
    
    // 초별로 체크
	while (true) {
        // 전부 확인 여부
		while (idx !=jobs.size()) {
            // 넣을 수 있는 것들(해당 초와 같다면 추가)
			if (jobs[idx][0] == now_time){
				pq.push(jobs[idx]);
				idx++; // 다음 것 탐색
			}
			else break;
		}
        
        // 작업종료 시 처리 가능한 경우
		if (remain <= 0 && !pq.empty()){
			temp = pq.top();
			pq.pop();
			remain = temp[1]; // 처리 시간
			total += temp[1]; // 해당 처리 시간 만큼 더하기
		}
		
        // 큐에 있던 것들 초당 개수별로 대기시간 더해지므로
		total += pq.size();
		remain--;
		now_time++;

        // 작업 완료시
		if (pq.empty() && remain == 0 && idx == jobs.size()) {
			break;
		}
	}
	return total / jobs.size();
}