1700번 멀티탭 스케줄링

문제 링크

멀티탭 스케줄링

문제 풀이

전기용품 사용순서를 탐색하면 다음과 같은 케이스가 존재한다.

1. 만약 멀티탭 중 비어있는 플러그가 있다면, 비어있는 곳을 사용한다.
2. 만약 현재 보고 있는 전기용품이 이미 플러그를 사용중이라면, 무시한다.
3. 만약 플러그를 사용중인 전기용품 중 더이상 사용하지 않을 물건이 있다면, 그 용품을 빼고 현재 전기용품을 플러그에 꽂는다.
4. 만약 플러그를 사용중인 전기용품 모두 나중에 다시 사용할 예정이라면, 제일 늦게 사용될 전기용품을 빼고 현재 사용할 전기용품을 플러그에 꽂는다.

전기용품의 사용순서를 저장하기 위해 각각의 전기용품마다 queue를 두어 순서를 저장하고 플러그에 꽂을 때마다 queue를 pop해준다. 위의 케이스에 맞게 구현하면 다음과 같다.

구현

#include <iostream> 
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int N, K;
queue<int> order[101];
vector<int> plug(101, 0), input(101, 0);

int solve() {
    int ret = 0;
    for (int i = 0; i < K; ++i) {
        int index = 0, late = -1;
        int pos = -1;
        bool flag = false;
        for ( ; index < N; ++index) {
            if (plug[index] == 0 || plug[index] == input[i]) {
                order[input[i]].pop();
                plug[index] = input[i];
                break;
            }
            else if (order[plug[index]].empty()) {
                flag = true;
                pos = index;
            }
            else if (!flag && late < order[plug[index]].front()) {
                late = order[plug[index]].front();
                pos = index;
            }
        }
        if (index == N) {
            order[input[i]].pop();
            plug[pos] = input[i];
            ++ret;
        }
    }
    return ret;
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> N >> K;
    for (int i = 0; i < K; ++i) {
        int a;
        cin >> a;
        input[i] = a;
        order[a].push(i);
    }

    cout << solve();
    return 0;
}