문제 개요
오늘의 코딩 테스트 문제는 '디스크 컨트롤러'다. 여러 작업 요청을 효율적으로 처리하여 평균 대기 시간을 최소화하는 문제다. 프로그래머스 힙(Heap) 파트에 속한 문제로, 실제 운영체제의 작업 스케줄링과 유사한 개념을 다룬다.
문제 분석
주요 요구사항은 다음과 같다:
1.
입력: [작업 요청 시점, 작업 소요시간]을 원소로 갖는 2차원 배열
2.
출력: 모든 작업의 요청부터 종료까지 걸린 시간의 평균값 (소수점 이하 버림)
3.
제약 조건:
•
하드디스크는 한 번에 하나의 작업만 수행 가능
•
작업을 수행하지 않을 때는 먼저 요청된 작업부터 처리
이 문제의 핵심은 작업 처리 순서를 어떻게 결정하느냐다. 단순히 요청 순서대로 처리하는 것보다 더 효율적인 방법을 찾아야 한다.
접근 방식
그리디(Greedy) 알고리즘과 우선순위 큐를 활용하기로 했다. 구체적인 접근 방식은 다음과 같다:
1.
작업 요청 시점을 기준으로 정렬된 큐를 생성
2.
현재 시점에서 처리 가능한 작업들을 별도의 우선순위 큐에 저장
3.
우선순위 큐에서 가장 짧은 작업 시간을 가진 작업을 선택하여 처리
이 방식을 선택한 이유는 다음과 같다:
•
항상 현재 시점에서 가장 효율적인 선택을 하므로 그리디 알고리즘의 특성을 만족
•
우선순위 큐를 사용하여 가장 짧은 작업을 빠르게 선택할 수 있음
•
요청 시점과 처리 시점을 분리하여 관리할 수 있음
코드 구현
코드의 주요 구조는 다음과 같다:
#include <string>
#include <vector>
#include <queue>
using namespace std;
struct comp
{
bool operator()(vector<int> a, vector<int> b)
{
if (a[1]>b[1])
return true;
return false;
}
};
int solution(vector<vector<int>> jobs) {
int answer = 0;
int time = 0;
priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> q_jobs(jobs.begin(), jobs.end());
priority_queue<vector<int>, vector<vector<int>>, comp> pq;
vector<int> results;
vector<int> work = {0, 0};
while (!q_jobs.empty() || !pq.empty())
{
while (!q_jobs.empty() && q_jobs.top()[0]==time)
{
pq.push(q_jobs.top());
q_jobs.pop();
}
if (work[1]==0 && !pq.empty())
{
work = pq.top();
pq.pop();
results.push_back((time - work[0]) + work[1]);
}
if (work[1]>0)
work[1]--;
time++;
}
int acc = 0;
for (auto t: results)
acc = acc + t;
answer = acc/results.size();
return answer;
}
C++
복사
주요 포인트:
1.
priority_queue를 두 개 사용: 하나는 요청 시점 정렬용, 다른 하나는 작업 시간 정렬용
2.
시간을 1씩 증가시키며 시뮬레이션
3.
각 시점마다 새로운 작업 요청을 확인하고, 처리 가능한 작업을 우선순위 큐에 추가
4.
현재 작업이 없을 때 우선순위 큐에서 가장 짧은 작업을 선택하여 처리
회고 및 학습점
while 루프가 길어서 더 작은 함수들로 분리하여 각 부분의 역할을 명확히 할 필요가 있을 것 같다.
이번 경험을 토대로, 앞으로는 문제 해결 전략을 세울 때 더 체계적인 접근을 할 것이다. 특히, 자료구조 선택의 근거를 더 명확히 하고, 시간 복잡도를 개선할 수 있는 방안을 초기 단계부터 고려해야겠다.
