멀티탭 스케줄링

코드

#include <string>
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <algorithm>
#include <deque>
#include <sstream>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    // 현재 plug에 있는 요소들 중 앞으로 안 쓰거나 나중에 사용되는 요소를 찾아서 대체
    map<int,deque<int>> m;
    vector<int> origin;
    vector<int> plug;
    int N, K, in, ans=0;
    cin >> N >> K;
    for(int i=0;i<K;i++)
    {
        cin >> in;
        m[in].push_back(i);
        origin.push_back(in);
    }
    for(int i=0;i<K;i++)
    {
        m[origin[i]].pop_front();
        // plug에 이미 꽃혀있으면 패스
        auto it = find(plug.begin(), plug.end(), origin[i]);
        if(it != plug.end())  continue;
        // 없는데 plug가 가득 안찼으면 삽입
        if(plug.size() < N){
            plug.push_back(origin[i]);
        }else{
            // 없는데 plug가 가득 찼을 때에 앞으로 안쓰거나 가장 나중에 사용되는 요소 찾아서 대체
            int idx=-1;
            int val=-1;
            for(int j=0;j<N;j++)
            {
                if(m[plug[j]].empty()){
                    val = plug[j];
                    break;
                }
                if(m[plug[j]].front() > idx){
                    idx = m[plug[j]].front();
                    val = plug[j];
                }
            }
            int IDX = find(plug.begin(), plug.end(), val) - plug.begin();
            plug[IDX] = origin[i];
            ans++;
        }
    }
    cout << ans;
    return 0;
}

• 이해
  : 해당 문제는 OPT라는 스케줄링 알고리즘 기법을 구현하면 해결되는 문제!
  (OPT란 ?
  페이징 대체 기법중 하나로 현재 유지하는 요소중 가장 마지막에 사용되는 요소를 대체해야 최적의 경우가 나오는 것!)

• 원리(opt 스케줄링 알고리즘)
  1) 각 전자기기의 번호별로 사용되는 인덱스를 map에 저장
  2) plug에 자리가 없을 때 plug에 꽂힌 요소들을 map을 돌면서 다음에 사용될 인덱스가 가장 크거나, 사용되지 않는것을 선택
  3) 선택한 플러그의 요소를 들어온 값으로 대체 (플러그 뽑는 행위!)

• 실수
  : 인덱스의 순서를 차례차례 저장한 m에서
  m[origin[i]].pop_front()을 해야하는데 m[origin[i]].pop_back()을함;
  (앞에서 빼려면 vector가 아니라 deque를 써야한다 바보야)