하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.
예를들어
- 0ms 시점에 3ms가 소요되는 A작업 요청
- 1ms 시점에 9ms가 소요되는 B작업 요청
- 2ms 시점에 6ms가 소요되는 C작업 요청
와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다.
한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다.
- A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms)
- B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms 시점에 작업 완료(요청에서 종료까지 : 11ms)
- C: 2ms부터 대기하다가, 12ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 16ms)
이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(= (3 + 11 + 16) / 3)가 됩니다.
하지만 A → C → B 순서대로 처리하면
- A: 3ms 시점에 작업 완료(요청에서 종료까지 : 3ms)
- C: 2ms부터 대기하다가, 3ms 시점에 작업을 시작해서 9ms 시점에 작업 완료(요청에서 종료까지 : 7ms)
- B: 1ms부터 대기하다가, 9ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 17ms)
이렇게 A → C → B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(= (3 + 7 + 17) / 3)가 됩니다.
각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)
제한 사항
jobs의 길이는 1 이상 500 이하입니다.
jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
string solution(string s, string skip, int index) {
string answer = "";
//sort 정렬 : 시간복잡도 N , 우선순위 큐 : 시간복잡도 : log n
//이기에 우선순위큐를 이용하여 minheap으로 정렬함
priority_queue<char,vector<char>,greater<char>> pq_skip;
for(char ch : skip) { pq_skip.push(ch);}
char pivot = 'a'; //알파벳 배열에 넣을 시작 문자
vector<char> alpabet;
while(pivot <= 'z')
{
//해당 알파벳이 skip문자열에 있는경우 알파벳 배열에 넣지 않는다.
if( pq_skip.top() != pivot) { alpabet.push_back(pivot); }
else { pq_skip.pop(); }
pivot++;
}
//문자열 s 길이만큼 순회하며 문자를 변환한다.
int result;
for(int i = 0; s.size() >i;i++)
{
//문자열 s의 단일문자가 알파벳배열의 어디에 위치하는지 찾는다.
int alpabet_index = find(alpabet.begin(),alpabet.end(),s[i]) - alpabet.begin();
//찾은 단일문자위치에 인자값index를 더하여 최종 위치를 찾는다.
result = alpabet_index + index;
//만약 알파벳 사이즈를 초과한 경우 , 알파벳 사이즈만큼 뺀다.
while(result> alpabet.size()-1 )
{
result -= alpabet.size();
}
answer += alpabet[result];
}
return answer;
}
해당 문제를 이렇게 풀었지만 , 다른 사람 풀이를 보니 더욱 가독성 좋고 쉽게 풀이한게 있어 코드를 첨부한다.
다른사람 풀이
#include <string>
#include <vector>
using namespace std;
string solution(string s, string skip, int index) {
string answer = "";
for(auto v : s)
{
int t = 0; //다음 문자로 넘어간 숫자를 카운트하는 변수
int c = v - 'a'; //문자v에서 'a'를 뺌으로 알파벳의 위치순서를 파악
while(t < index)
{
c++;//다음 알파벳위치(알파벳 변환)
v = (c % 26) + 'a';//해당 알파벳 위치를 문자열로 변환(v는 char 자료형)
//c%26은 알파벳이 총 26개 이기 때문에 큰 숫자가 들어와도 알파벳의 한 형태로 변환 가능하기떄문
//skip문자열에 해당 문자(v)가 있는지 체크
if(skip.find(v) == string::npos)
{
//없으면 카운트를 증가시킴
t++;
}
}
answer += v;
}
return answer;
}
#include <string>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
//체육복 빌려주는 조건 : 자기 앞,뒷 1번호 만큼 가능
//체육수업을 들을수있는 학생의 최댓값 return
//여벌 체육복을 가져온 학생도 도난 가능,체육복을 빌려줄수 없음 하지만 자기것는 있음
bool reserve_check(int index, map<int,int>& students)
{
//iter = 자신의 앞 또는 뒤 학생의 iter
map<int,int>::iterator iter_before = students.find(index);
//해당 학생이 없을수도 있기에(제일 앞학생 또는 제일 뒷학생 고려)
//여벌 체육복이 있으면 해당 학생의 체육복을 -1 시킴
if(iter_before != students.end() && iter_before->second == 2)
{
iter_before->second--;
return true;
}
return false;
}
int solution(int n, vector<int> lost, vector<int> reserve) {
int answer = 0;
map<int,int> students; //학생번호,체육복 수
//여벌 체육복이 있는 학생을 맵에 추가
for(int num : reserve) { students.insert({num,2}); }
//체육복을 잃어버린 학생을 맵에 추가
for(int num : lost)
{
//해당 맵에 여벌 체육복을 갖고 있지만 잃어버린 학생이 있을수 있기에 find 실행
map<int,int>::iterator iter = students.find(num);
//find결과가 없으면 해당 체육복이 없는 학생으로 추가
if(iter == students.end()) { students.insert({num,0}); }
//find 결과가 있으면 해당 학생의 체육복 수를 1감소
else { iter->second--;}
}
for(int i=1; i <= n ; i++)
{
map<int,int>::iterator iter = students.find(i);
//해당 학생이 map에 없으면 수업을 들을 수 있기에 answer후 순회
if(iter == students.end()) { answer++; continue;}
//해당 학생이 체육복이 없는경우
if(iter->second == 0)
{
//자기 앞,뒷 번호의 여벌 체육복을 체크후 true인경우 해당 학생의 체육복을 1증가
if(reserve_check(i-1,students) || reserve_check(i+1,students)) iter->second++;
}
//해당 학생이 체육복이 1개 이상인경우 answer증가
if(iter->second >=1) { answer++; }
}
return answer;
}
