[ICPC] 백준 1700 - 멀티탭 스케줄링

www.acmicpc.net/problem/1700

풀이

정해는 OS분야에서 고안되었으나 사용하지 못하는 최적 페이지 교체 알고리즘이다.

 

멀티탭이 가득 찼을 때 꽃힌 전기용품 중에서 가장 늦게 사용될 물건을 빼버린다는 것인데 이 말은 전체에서 마지막으로 나타나는 전기용품이 아니라 다음에 쓸 전기용품 중 처음으로 등장했을 때 그 순서가 가장 늦은 용품을 빼는 것이다.

 

물론 더이상 쓰지 않을 물건은 최우선으로 빼줘야 한다.

구현

어떤 용품의 사용횟수가 얼마나 남았는지 mp배열로 저장해준다.

 

멀티탭에 어떤 용품이 꽃혔는지 셋으로 관리하면서 멀티탭이 가득차지 않았거나 꽃혔던 물건을 사용한다면 해당 용품을 셋에 삽입하여 넘어간다.

 

플러그를 뽑아야만 한다면 먼저 사용을 다 한 물건이 있는지 확인해주고 그렇지 않다면 맵을 이용하여 각 물건이 다음으로 쓰이는 첫번째 위치를 저장한 다음 벡터를 통해 정렬하여 마지막 원소를 제거해주는 방식으로 구현했다.

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
using pii = pair<int, int>;
 
int n, k;
int ar[100];
int mp[101];
unordered_set<int> st;
int cnt;
 
int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
 
    cin >> n >> k;
 
    for (int i = 0; i < k; ++i)
    {
        cin >> ar[i];
        ++mp[ar[i]];
    }
 
    for (int i = 0; i < k; ++i)
    {
        if (st.size() < n || st.count(ar[i]))
        {
            st.insert(ar[i]);
            --mp[ar[i]];
            continue;
        }
 
        bool swapped = false;
 
        for (int item: st)
        {
            if (!mp[item])
            {
                st.erase(item);
                swapped = true;
                break;
            }
        }
 
        if (!swapped)
        {
            unordered_map<int, int> order;
            vector<pii> v;
 
            for (int j = i; j < k; ++j)
                if (st.count(ar[j]) && !order.count(ar[j]))
                    order[ar[j]] = j;
            
            for (auto it = order.begin(); it != order.end(); ++it)
                v.push_back({it->second, it->first});
            sort(v.begin(), v.end());
            st.erase(v.back().second);
        }
 
        --mp[ar[i]];
        st.insert(ar[i]);
        ++cnt;
    }
 
    cout << cnt;
}