[TopCoder] Batchsystem(배치 시스템)
2023. 3. 1. 16:39ㆍAlgorithm
과거에는 전체 조직이 모든 계산 작업을 수행하기 위해 하나의 큰 컴퓨터에 의존했습니다. 시스템에는 대기 중인 작업 목록이 있으며 기간 및 사용자별로 설명되어 있습니다. 보류 중인 작업이 있으며 각 작업은 이 두 배열로 설명됩니다. i번째 작업의 경우 duration[i]은 작업을 완료하는 데 필요한 총 시간(분)이며 user[i]는 해당 작업을 요청한 사용자를 식별하는 문자열입니다. 사용자는 여러 작업을 요청할 수 있습니다. 컴퓨터는 한 번에 하나의 작업만 처리할 수 있습니다. 사용자의 대기 시간은 사용자가 요청한 모든 작업이 완료될 때까지 기다려야 하는 시간으로 정의됩니다. 프로그램은 모든 사용자의 평균 대기 시간을 최소화하는 방식으로 작업을 예약해야 합니다.
n 작업의 0 기반 인덱스를 포함하는 int[]를 처리해야 하는 순서대로 반환합니다. 여러 개의 결과가 있을 경우 먼저 나온 결과를 사전 형식으로 반환합니다.
Definition
Class:
BatchSystem
Method:
schedule
Parameters:
vector <int>, vector <string>
Returns:
vector <int>
Method signature:
vector <int> schedule(vector <int> duration, vector <string> user)
(be sure your method is public)
Examples
0)
{400, 100, 100, 100}
{"Danny Messer", "Stella Bonasera", "Stella Bonasera", "Mac Taylor"}
Returns: {3, 1, 2, 0 }
In total, Mac Taylor will have to wait 100 minutes, Stella Bonasera 300 minutes and Danny Messer 700 minutes. The best average time is approximately 366.66 minutes.
1)
{200, 200, 200}
{"Gil", "Sarah", "Warrick"}
Returns: {0, 1, 2 }
2)
{100, 200, 50}
{"Horatio Caine", "horatio caine", "YEAAAAAAH"}
Returns: {2, 0, 1 }
인원들의 전체 대기 시간을 최소화하기 위해서는 가장 작업 시간이 작은 사람부터 먼저 처리해주어서
대기 큐를 빨리 빨리 해소시켜주어야 한다.
마치 손자병법에서 '가장 약한 적부터 처리하라' 라고 하는 것과 같은 원리이다.
문제는 전체 작업시간이 같은 사람이 나타날 수 있다는 것이고, 순서는 사전 순서에 맞게 반환해야 한다는 것이다.
먼저 사람 당 대기시간 총합을 계산하기 위해 C++의 map 자료형을 이용한다.
class BatchSystem{
public:
vector<int> schedule(vector<int> duration, vector<string> user){
int N = duration.size();
map<string, long long> jobTime;
for(int i=0; i<N; i++){
jobTime[user[i]] += duration[i];
//전체 순회하여 map 갱신
//user마다의 전체 duration 계산
}
JobTime에는 사람 : 전체duration 이 저장된다.
vector<bool> done(N);
// 전체 duration의 sorting을 위한 고려요소
vector<int> ans;
done 벡터를 통해 대기 큐에서 이 사람이 이미 빠졌는지 여부를 체크한다.
while(ans.size()<N){
string minMan;
//가장 최소의 duration합을 가진 사람
for(int i=0; i<N; i++){
if(!done[i] && (minMan.empty() || jobTime[user[i]] < jobTime[minMan])){
// 고려대상에 있는 사람들 중 가장 작은 duration합을 가진 사람을 찾는다.
// for문 처음 진입 시에는 가장 첫번째 사람을 minMan으로 설정.
minMan = user[i];
//jobTime[user[i]] < jobTime[minMan]으로 하면
//jobTime이 같은 사람이 뒤에 나타나도
//사전순서에 맞게 정렬된다
}
}
for(int i=0; i<N; i++){
if(user[i] == minMan){
done[i] = true;
ans.push_back(i);
}
}
}
먼저 배열의 전체를 순회하여 가장 작은 duration을 가진 사람을 찾고,
대기 큐에서 이 사람에 해당하는 작업 순번을 ans에 저장한다. 그리고 대기 큐에서 제외(done[i] = ture)한다.
ans가 N번째 요소까지 찰 때까지 이를 반복한다.
'Algorithm' 카테고리의 다른 글
[TopCoder] CirclesCountry (원형 국가) (0) | 2023.03.01 |
---|---|
[TopCoder] AutoLoan (자동차 할부) (0) | 2023.03.01 |
[TopCoder] StockHistory (주식 히스토리) (0) | 2023.03.01 |
[TopCoder] ColorfulBoxesAndBalls (알록달록 상자와 공들) (0) | 2023.02.26 |
[TopCoder] HandsShaking(악수) (1) | 2023.02.25 |