메모장

문제 풀이 :

모든 작업의 요청 시점 시간 에서부터 작업이 완료되는 시간들의 평균값을 구하는 문제다.

문제는 Heap(힙) 카테고리에 있지만 우선순위 큐를 사용하지 않아도 풀리는 문제다.

첫번째 중요한점 : 평균은 최소의 원소끼리 합했을때 최소의 평균값이 나온다.

즉, 인자값으로 준 vector를 [작업의 소요시간]을 기준으로 오름차순 정렬을 해서 각 평균을 구하면 된다.

두번째 중요한 점 : [ 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다 ]

이 문장을 잘 봐야된다.  작업이 완료된 시점의 시간에 작업이 없으면 남은 작업 중 요청 시점이 제일 빠른것 부터 다시 평균을 구해주면된다. 

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

using namespace std;

bool compare(vector<int> a , vector<int> b)
{
     return a[1] < b[1];  
}

int solution(vector<vector<int>> jobs) 
{
    int answer = 0;
    int cur_time =0;
    bool check = false;
    
    vector<vector<int>> results = jobs;

    while(!results.empty())
    {
        check = false;
        sort(results.begin(),results.end(),compare);
        for(int i = 0; i < results.size(); i++)
        {
            if(cur_time >= results[i][0])
            {
                check  = true;
                answer += (cur_time - results[i][0]) + results[i][1];
                cout << cur_time << " "<< results[i][0]<< " "<<results[i][1]<<endl;
                cur_time += results[i][1];
                results.erase(results.begin() + i);
                break;
            }
        }

        if(!check)
        {
            vector<vector<int>> tmp = results;
            sort(tmp.begin(),tmp.end());
            cur_time = tmp[0][0];
            answer += tmp[0][1];
            cout << cur_time << " "<< tmp[0][0]<< " "<<tmp[0][1]<<endl;
            cur_time += tmp[0][1];
            tmp.erase(tmp.begin());
            results = tmp;
        }
    }
    
  cout <<answer;
    
    return answer / jobs.size();
}

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

//알고리즘 헤더에 sort 함수에 비교자 변경해서 풀었음
//비교자에서 해당 수자를 문자열로 바꾸고 문자열 제일 앞 숫자가 같으면
//해당 숫자문자열을 합친뒤 크기를 비교하여 true인경우 정렬을 하는식으로

//비교자의 해당 숫자의 문자열 앞이 다른경우 대소비교하여 true인경우 정렬 

using namespace std;

bool compare(int a, int b)
{
     string str_lhs = to_string(a) ;
     string str_rhs = to_string(b) ;
    
    switch(str_lhs.front() == str_rhs.front() )
    {
        case true:
            if(str_lhs+str_rhs > str_rhs + str_lhs) { return true;}
            break;
        case false:
            if(to_string(a).front() > to_string(b).front())  {return true;} 
            break;
    }
  
    return false;
}

string solution(vector<int> numbers) {
    string answer = "";
        
    sort(numbers.begin(),numbers.end(),compare);
   
    //정렬된 배열 제알 앞이 0인경우 숫자 완성이 안됬기에 0문자열 리턴 
    if(numbers.front() == 0 ) { return "0";}
    
    for(int num : numbers) {  answer += to_string(num);}

    return answer;
}

#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 <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;
}

#include <string>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

//1.메인벨트와  적재 박스 비교
//2.같은경우 벨트와 적재박스 큐에서 제외 후 ,answer증가
//3.다른경우 서브벨트 top과 비교해서 같은경우 stack과queue에서 제외후 answer증가
//3.둘다 다른경우 서브벨트에 적재

int solution(vector<int> order) {
    int answer = 0;

    queue<int> q_order; // 기사님이 원하는 택배 순서
    queue<int> main_belt;// 메인 컨테이너벨트
    stack<int> sub_belt; // 서브 컨테이너벨트
    
    //택배차의 원하는 택배순서를 queue로 저장
    for (int i = 0; i < order.size(); i++)
    {
        main_belt.push(i + 1); 
        q_order.push(order[i]); 
    }

    while (!q_order.empty())
    {
        //메인 벨트의 택배와 택배차의 order list와 비교
        if (!main_belt.empty() && q_order.front() == main_belt.front())
        {
            answer++;
            q_order.pop();
            main_belt.pop();
        }
        //서브 벨트의 택배와 택배차의 order list와 비교
        else if (!sub_belt.empty() && q_order.front() == sub_belt.top())
        {
            answer++;
            q_order.pop();
            sub_belt.pop();
        }
        //메인 벨트의 서브 벨트 둘다 택배가 없는경우
        else
        {
            //메인 벨트에 택배가 있으면 서브벨트에 해당 택배를 보관 후 다시 순회
            if (!main_belt.empty())
            {
                sub_belt.push(main_belt.front());
                main_belt.pop();
            }
            //메인 벨트에 택배가 없으면 더이상 할 수 없으므로 탈출후 반환
            else { return answer; }
        }

    }

    return answer;
}