22.06.04. 풀었던 문제들

1. 보석 쇼핑

투포인터로 푸는 문제.

처음 접근은 제일 뒤에서부터 앞으로 당길 수 있을 만큼 당기고 이후에 앞에서 밀 수 있을 만큼 뒤로 미는 방식을 택했는데 반례가 존재해 다른 풀이로 풀어야만 했다.

다음 접근은 start, end를 0으로 두고 end를 1칸씩 뒤로 민다. 그리고 start~end-1 사이에 보석별 개수를 담는 map um을 뒀고 um에 2를 초과하는 값이 있다면 뒤로 민다. 그리고 같은 길이라면 앞에 있는 것을 가져오기 때문에 min_len > e-s라는 것을 해야 하고, 또 s~e 사이에 모든 보석이 있어야 하므로 다음과 같은 식을 취했다.

다만 처음에는 end를 -1로 두고 while(e < gems.size()-1)을 취했는데(e가 제일 마지막 index를 가리키는 방식으로) while문 통과를 안 한다. 미쳐버리는 줄 알았다. 왜지? -> vector size는 unsigned이고 int는 signed라서 그렇다.

// 보석 쇼핑

#include <string>
#include <vector>
#include <unordered_map>
#include <set>

using namespace std;

vector<int> solution(vector<string> gems) {
    unordered_map<string, int> um;
    
    set<string> set_gem;
    for(string s : gems) set_gem.insert(s);
    int gem_num = set_gem.size();

    int s = 0, e = 0, s_answer, e_answer, min_len = 100001;

    while(e < gems.size()){
        um[gems[e]]++; e++;
        while(um[gems[s]] > 1 && s < e){
            um[gems[s]]--; s++;    
        }
        if(min_len > e - s && um.size() == gem_num){
            e_answer = e;
            s_answer = s + 1;
            min_len = e - s;
        }
    }
    return {s_answer, e_answer};
}

/*
vector<int> solution(vector<string> gems) {
    unordered_map<string, int> um;
    
    set<string> set_gem;
    for(string s : gems) set_gem.insert(s);
    int gem_num = set_gem.size();

    int s = 0, e = -1, s_answer, e_answer, min_len = 100001;

    while(e < gems.size()-1){
        e++; um[gems[e]]++; 
        while(um[gems[s]] > 1 && s <= e){
            um[gems[s]]--; s++;    
        }
        if(min_len > e - s + 1 && um.size() == gem_num){
            e_answer = e;
            s_answer = s;
            min_len = e - s + 1;
        }
    }
    return {s_answer + 1, e_answer + 1};
}*/

 

2. 선입 선출 스케줄링

먼저 어떤 시간 t가 있을 때, t까지 '완성된 작업 수'가 아니라 t까지 '완성 + 진행 중인 총 작업 수'를 구할 수 있다. 이렇게 생각하는 이유는 t=0일 때 모든 core에 작업을 넣기 때문이다. 이는 [t - cores.size()] + [for c : cores t/cores]로 구할 수 있다. t인 시점에 몇 개의 작업이 진행중인지 알 수 있다는 것... 그리고 언제 작업이 끝나는지를 묻는 게아니라 몇 번째 core가 작업을 마지막으로 진행하는지가 중요하기 때문에 현재 진행 중인 작업 수를 구하는 것이 유의미하다. 아무튼 이렇게 t를 구한다. 일이 끝나는 시점의 t를 구하지 않는 이유는 c1, c2의 공배수가 t일 경우 뭐가 먼저 시작되었는지 알 수 없기 때문에, 현재까지 진행 중인 총 작업 수가 n보다 크거나 같은 t의 lower bound를 구하는 것이다. - 이 아이디어를 도출하는 게 중요했다.

t를 lower bound로 구하면 t-1시간까지 진행된 작업 개수를 구하고 n에서 이 값을 뺀다. 그러면 남은 작업은 모두 t시간에 진행되며, t시간에 작업을 받을 수 있는 core(t%cores[i] == 0)를 모두 더해 진행된 작업 수가 n이 되는 시점의 core가 n번째 작업을 받는 core이다.

// 선입 선출 스케줄링

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

using namespace std;


bool work(int total_works, int time, vector<int>& cores){
    int num_works = 0;
    for(int c : cores){
        num_works += time/c;
    }
    
    if(total_works <= num_works + cores.size()) return true;
    else return false;
}

int solution(int n, vector<int> cores) {
    if(n < cores.size()) return n;
    
    int time = cores[cores.size()-1] * n;
    int s = 1, e = time, mid;
    
    while(s < e){
        mid = (s + e) / 2;
        if(work(n, mid, cores)){
            e = mid;
        }
        else s = mid+1;
    }
    
    n -= cores.size();
    for(int c : cores){
        n -= (e-1)/c;
    }
    for(int i = 0; i<cores.size(); i++){
        if(e % cores[i] == 0)n--;
        if(n == 0) return i+1;
    }
    
    return 1;
}