programmers) 힙(heap) / 디스크컨트롤러

 

최근 프로그래머스라는 사이트를 알게 되었고 해당 사이트에 나와있는 연습문제를 하나씩 풀어 보는 재미로 군생활을 녹이고 있다 ㅎ

코딩을 아두이노로 시작한 비전공자에게 자료구조란 생전 처음 보는 친구였다.

Programmers 라는 사이트는 코딩 테스트에서 주로 출제되는 유형별로 묶어두었고, 덕분에 갈래를 잡고 공부하는데 많은 도움이 되었다.

이번 포스팅에서 풀어볼 문제는 아래 링크를 통해 확인할 수 있다. 

 

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

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

C++ 이 무슨 언어인가?  바로 객체지향 언어이다. 

그러므로 문제를 객체지향적 관점에서 해결해 보았다. ^^ 

그냥 푼 답안은 이미 인터넷에 검색하면 많이 나올것이다ㅎㅎ

문제를 정리하면 아래 세 문장으로 정리할 수 있다.

 

입력되는 데이터들을 하드디스크의 대기목록에 저장한다.

입력 데이터의 작업 소요시간은 동일하지 않다.

하드디스크는 처리 평균시간이 최소가 되도록 순서를 바꿔 처리한다.

 

이 문장으로부터 키워드를 잡아보았다.

 

입력되는 데이터( {요청된시점, 작업소요시간} ) 들을 하드디스크(객체 disk)의 대기목록(queue) 저장한다.

입력데이터의 작업 소요시간은 동일하지 않다.

하드디스크는 평균 대기시간(요청~처리 시점)이 최소가 되도록 순서를 바꿔 처리한다.

1. 접근 과정

1. 문제에서 입력해준 작업목록(jobs)을 요청시간 순으로 정렬후 시간증가에 맞춰 디스크컨트롤러에 제공한다.

point)

처음 입력된 데이터를 저장한후 1회만 정렬하면 되므로 sort 알고리즘 사용

 

2. 디스크컨트롤러에 요청된 데이터(req)를 우선순위에 맞춰 저장한다.

point )

req  컨테이너는 지속적으로 데이터가

추가(시간증가), 삭제(처리완료), 정렬(우선순위) 된다.

효율성을 고려하여 heap 정렬을 사용하는 queue를 채택한다.

-> priority_queue ( req 선언)

 

3. 위 요소를 바탕으로 diskcontroller의 입장에서 run 함수를 작성하였다.

    -> jobs(작업목록),  req(하드에 요청된 목록)

 

run 함수

시간(time)을 반영해  작업목록(jobs)으로 부터 작업목록큐(req)에 추가 

작업목록큐(req)에 처리되지 않은 작업이 있는지 확인

   1) 요청된 작업이 없으면(req.empty == True)

   작업목록(jobs)을 참조하여 시간(time) 이동

   2) 요청된 작업이 있으면 

   요청된 목록(req)를 참조하여 해당 작업이 끝나는 시점으로 시간이동 (time += 작업 소요시간 )

   해당작업의 대기시간(완료시점 - 요청시점) 만큼 작업별 대기시간(proccesing_time)에 누적

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

class disk{
	private:
	//time
	int time = 0;
	//input data
	vector< vector<int>> jobs;
	int jobs_index =0;
	int jobs_size;

	
	//작업별 대기시간 합
	int proccesing_time= 0;
	

	// 디스크 컨트롤러 작업목록 큐 (priority_queue)
	struct comp2{ // 우선순위 옵션2: 작업소요시간이 짧은 순으로 처리
	bool operator()(vector<int> v1, vector<int> v2){
		return v1[1] > v2[1];}
	};	
	priority_queue< vector<int>, vector< vector<int> >, comp2 > req;

	private:
	void get_req(int mytime){ // 현재시간(mytime) 까지 요청된 작업을 req 큐에 입력
    	if (jobs_index == jobs_size)
			return;	
		for (jobs_index; jobs[jobs_index][0] <= mytime  ; jobs_index++){
			req.push(jobs[jobs_index]);
			cout << "new req idx) " << jobs_index <<", req_t) "<< jobs[jobs_index][0]<<", proc_t) " <<jobs[jobs_index][1] <<endl;
		}
	}	
	
	public:
	void __init(vector<vector<int>> myjobs){
		jobs_size = myjobs.size();
		jobs = myjobs;
		
		struct comp{ // 우선순위 옵션1: 요청시간 순으로 정렬
		bool operator()(vector<int> v1, vector<int> v2){
			return v1[0] < v2[0];}
		};
		sort(jobs.begin(), jobs.end(), comp()); // 입력된 데이터를 우선순위 옵션1(요청시간이 빠른순)로 정렬
	}

	int run(){
		do{
			get_req(time);
			cout << "now time:" << time << endl;
			if (req.empty()){ // 현재 작업대기중인 작업이 없음 -> 다음 작업요청까지 대기(시간이동)
				time = jobs[jobs_index][0]; 
			}
			else{// 현재 작업대기중인 작업이 있음
				time += req.top()[1];  // 가장 우선순위가 높은 작업 시작, 해당작업이 끝나는 시점으로 시간이동
				proccesing_time += (time - req.top()[0]); // 완료한 작업의 대기시간 누적
				cout << "end req -> "<< req.top()[0] <<","<< req.top()[1]<< endl;
				req.pop(); // 완료한 작업 제거
			}
		}
		while(!req.empty() || jobs_index+1 < jobs_size); // overflow 방지
		
		return proccesing_time/jobs_size; // 평균 작업 대기시간 반환
	}
	
};


int main (){
	cout << "start" << endl;
	vector<vector<int> > jobs= {{0,3}, {1,9}, {4,6},{4,6},{9,6},{12,6},{6,6}, {66,1} };
	
	disk di;
	di.__init(jobs);
	cout << "answer" << di.run() << endl;
	
}

 

+ps)

비가 많이 온 후로 사지방에 인터넷이 끊겨서 2주일 동안 들어오지 못했습니다... 죄송합니다....

2021년에 이게 말이 되는 소린가 싶지만 실제로 그랬습니다 ㅠㅠ