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

문제 풀이

 

 

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

using namespace std;

// 두 번째 원소로 정렬하기 위함.
// a < b 는 오름차순, a > b는 내림차순이다.
bool cmp(vector<int> a, vector<int> b){
	return a.back() < b.back();
}

int solution(vector<vector<int>> jobs) {
    // 작업의 시작 시간
	int start = 0;
	// 작업의 개수
	int jobs_cnt = jobs.size();
	
	//소요시간이 낮은 순으로 정렬
	sort(jobs.begin(), jobs.end(), cmp);
	
	// 배열이 빌 때까지
	while (!jobs.empty()) {

		// 현재 jobs는 소요시간을 기준으로 정렬된 상태. 이제 여기에서 시작시간이 작은 순으로 찾는 작업을 한다.
		for (int i = 0; i < jobs.size(); i++) {

			// 시작시간보다 작거나 같은 값을 찾는다.소요시간은 이미 정렬되어 있기 때문에
			// 시작시간이 같거나 낮은 값 중 가장 소요시간이 작은 순으로 나오게 된다
			if (jobs[i][0] <= start) {

				// 현재 진행중인 업무의 소요시간을 더해 작업의 종료 시간, 즉 다음 업무의 시작 시간을 업데이트한다.
				start += jobs[i][1];

				// 현재 작업은 jobs[i][0], 작업이 들어온 시점부터 대기하고 있었다.그 이전에는 현재 작업이 존재하지 않았기 때문에
				// 작업이 들어온 시점(jobs[i][0])을 전체에서 빼주면 대기시간을 포함한 현재 작업의 소요 시간이 남게 된다.
				answer += start - jobs[i][0];
				
				// 완료한 작업을 제거 후 반복문 탈출
				jobs.erase(jobs.begin() + i);
				break;
			}
			// 이전 작업이 종료되었음에도 다음 작업이 들어오지 않았을 경우
			if (i == jobs.size() - 1)
				// 시작 시간을 증가시킨다. 작업이 들어오지 않는 상태라도 시간은 계속 흐르기 때문.
				start++;
		 }
	}
	// 평균을 구하고 소수점 이하의 수를 버린다. 둘 다 int형이기 때문에 소수점은 알아서 버려진다.
	answer /= jobs_cnt;
    return answer;
}

 

해당 문제는 제가 직접 풀지는 못했고, 파이썬으로 푸셨던 johnyejin 님의 포스팅을 참고하였습니다. 해당 링크는 하단에 같이 게시하겠습니다. 

 

참고 포스팅

johnyejin.tistory.com/132

[Python][힙] 프로그래머스 - 디스크 컨트롤러(LEVEL3)

 

문제 링크

 

programmers.co.kr/learn/courses/30/lessons/42627?language=cpp

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