취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 20136번 문제인 멀티탭 스케줄링 2이다.
문제는 아래 링크를 확인하자.

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

Bélády's algorithm(Optimal page replacement algorithm)과 그 구현을 묻는 문제이다.

이 알고리즘에 따르면, 현재 멀티탭에 더 꽂을 공간이 없을 때 빼야 할 물건은 "앞으로 가장 나중에 사용하게 될 물건"이 된다. 앞으로 더 사용하지 않는다면 무한대의 시간 뒤에 사용하게 된다고 생각하자.

Bélády's algorithm에 대한 내용은 다음 링크를 참고하자:

https://en.wikipedia.org/wiki/Cache_replacement_policies#B%C3%A9l%C3%A1dy's_algorithm

https://en.wikipedia.org/wiki/Page_replacement_algorithm#The_theoretically_optimal_page_replacement_algorithm

이러한 알고리즘은 "앞으로 다음에 이 물건을 얼마나 나중에 사용하는가"를 우선순위로 한 우선순위 큐(priority queue)를 이용하여 효율적으로 구현할 수 있다.

아래는 제출한 소스코드이다.

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

struct process {
    int type;
    int next;
};

struct comp {
    bool operator() (process p1, process p2) {
        return p1.next < p2.next;
    }
};

process t[500001];
vector<bool> visited(500001);
int arr[500001];

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

    int N, K; cin >> N >> K;
    
    for (int i = 1; i <= K; i++) {
        int x; cin >> x;
        t[i].type = x;
        t[i].next = 1000000;
        t[arr[x]].next = i;
        arr[x] = i;
    }

    int cnt = 0, ans = 0;
    priority_queue<process, vector<process>, comp> pq;

    for (int i = 1; i <= K; i++) {
        if (visited[t[i].type]) pq.push(t[i]);
        else if (cnt < N) {
            cnt++;
            visited[t[i].type] = 1;
            pq.push(t[i]);
        }
        else {
            ans++;
            while (!visited[pq.top().type]) pq.pop();
            visited[pq.top().type] = 0; pq.pop();
            visited[t[i].type] = 1;
            pq.push(t[i]);
        }
    }

    cout << ans;
}