[Baekjoon,1700] 멀티탭 스케줄링

현재 사용해야 하는 기기를 맞이했을 때 다음과 같은 세 가지로 행동을 분류할 수 있다.

1. 꽂을 자리가 남는 경우
   -> 현재 기기를 꼽는다.
2. 이미 현재 기기가 꽂혀 있는 경우
   -> 아무것도 하지 않는다.
3. 하나를 뽑아야 하는 경우
   a. 현재 꼽혀있는 기기 중 나중에 안쓰이는 기기를 찾아 뽑는다.
   b. 안쓰이는 기기가 없다면 비교적 나중에 쓰이는 기기의 코드를 뽑는다.

구현

이를 구현한 코드를 아래에서 볼 수 있다. $set \ \ container$를 이용하여 해결하였다. 눈여겨 볼 부분은 나중에 쓰이지 않는 코드의 값을 $INF$로 설정하여 따로 처리하지 않는 부분이다.

#include <iostream>
#include <set>
using namespace std;

const int INF=987654321;

int main()
{
    int capacity,k;
    int plug[101];
    
    cin>>capacity>>k;
    for(int i=0;i<k;++i)
        cin>>plug[i];
    
    set<int> plugged;
    int ret=0;
    for(int i=0;i<k;++i)
    {
        // 꽂을 칸이 남은 경우 
        if(plugged.size()<capacity)
            plugged.insert(plug[i]);
        // 이미 해당 기기가 꽂혀있는 경우 
        else if(plugged.count(plug[i])>0)
            continue;
        // 하나를 뽑아야 하는 경우 
        else
        {
            set<int>::iterator it;
            // 나중에 안쓰이거나 가장 늦게 꼽히는 플러그를 찾는다. 
            // <쓰일 순서, 인덱스>
            pair<int,int> late=make_pair(-1,-1);
            // 꼽혀있는 기기 중 찾는다.
            for(it=plugged.begin();it!=plugged.end();++it)
            {
                // it 번째 플러그가 얼마나 나중에 이용되나 카운트 
                pair<int,int> here=make_pair(INF,*it);
                for(int j=i+1;j<k;++j)
                    if(*it==plug[j])
                    {
                        here.first=j;
                        break;
                    }
                // 더 늦게 이용되면 갱신한다.
                if(late.first<here.first)
                    late=here;
            }
            // 선택된 플러그를 뽑는다. 
            plugged.erase(plugged.find(late.second));
            plugged.insert(plug[i]);
            ++ret;
        }
    }
    cout<<ret<<endl;
    return 0;
}