[BOJ/20136] 멀티탭 스케줄링 2

🔗 링크

https://www.acmicpc.net/problem/20136

20136번: 멀티탭 스케줄링 2

🤯 한줄 후기

누가 멀티탭에 50만개나 꽂아요 ㅡㅡ

🤷 문제

👩‍💻 풀이

제한된 멀티탭 구멍 개수에 전기 용품을 꽂을 때 어떻게 꽂아야 효율적으로 할 수 있는지 구하는 문제이다.

효율적이란건 다른 전기 용품을 쓰려고 빼는 횟수를 줄이는 것을 말한다.

즉, 많이 나오면서 더 최근에 나오는 용품들은 미리 안빼놓고 있는게 이득이다.

우선순위 큐를 사용하면서 풀면 되는데, 처음에 생각 한 건 멀티탭 자체를 우선순위 큐로 구현하고, 그리디하게 더 많이 나오는 용품들을 계속 꽂아두는 방법을 생각했다.

하지만 이 방법은 많이 나오는 용품이 맨 뒤에 몰려 있으면 소용이 없다.

따라서 더 먼저 나오는 용품들도 생각을 해줘야한다.

큐 하나를 더 만들어서 해당 전기 용품이 나타나는 인덱스를 모두 넣어줬다.

그러고 우선순위 큐(멀티탭)에는 해당 전기 용품의 이름, 해당 전기 용품이 다음에 나올 인덱스 번호 를 저장해주었다.

큐의 우선순위는 인덱스가 더 뒤인 (높은) 순서대로이다. 

그러면 한번에 교환할 전기 용품을 알게 된다. 즉, 더 뒤에 나오는 전기 용품을 먼저 빼버리는 방식이다.

 

주의할 점은, 이미 꽂혀있는 경우인데 나 같은 경우는 visit 배열을 사용하여 꽂혀있으면 1로 바꾸고 빠지면 다시 0으로 바꿔주었다.

꽂혀 있는 경우에는 다음에 나올 인덱스를 갱신해줘야하는데, 이 점은 사실 그냥 push해도 상관이없다.

왜냐하면 큐는 무조건 인덱스 내림차순으로 정렬한다.

따라서 이전에 이미 들어가 있는 전기 용품은 지금 들어갈 인덱스보다 더 낮기 때문에 큐의 top으로 부터 더 내려갈 것이다.

그렇기 때문에 이건 생각하지 않고 그냥 push해버려도 상관이 없다.

💻 코드

//AC
//BOJ 20136 멀티탭 스케쥴링2
#include <iostream>
#include <vector>
#include <queue>
#define SIZE 500001
#define INF 987654321
using namespace std;
struct Multi{
    int name; int idx;
};
struct Cmp{
    bool operator()(const Multi &a, const Multi &b){
        return a.idx < b.idx;
    }
};
priority_queue<Multi, vector<Multi>, Cmp> tap;
priority_queue<int, vector<int>, greater<int> > q[SIZE];
int arr[SIZE];
int visit[SIZE];
int main(){
    int N, K, n, ans = 0, cnt = 0;
    cin >> N >> K;
    for(int i=1; i<=K; i++){
        scanf("%d", &n);
        arr[i] = n;
        q[n].push(i);
    }
    for(int i=1; i<=K; i++){
        if(visit[arr[i]]){
            q[arr[i]].pop();
            if(!q[arr[i]].empty())  tap.push({arr[i], q[arr[i]].top()});
            else    tap.push({arr[i], INF});
            continue;
        }
        if(cnt < N){
            q[arr[i]].pop();
            if(!q[arr[i]].empty())  tap.push({arr[i], q[arr[i]].top()});
            else{
                tap.push({arr[i], INF});
            }
            cnt += 1;
            visit[arr[i]] = 1;
        }
        else{
                Multi prev = tap.top();
                visit[prev.name] = 0;
                tap.pop();
                q[arr[i]].pop();
                if(!q[arr[i]].empty())  tap.push({arr[i], q[arr[i]].top()});
                else    tap.push({arr[i], INF});
                visit[arr[i]] = 1;
                ans += 1;
            }
        
    }
    printf("%d", ans);
    return 0;
}