[Algorithm] 백준 1700번: 멀티탭 스케줄링

운영체제를 열심히 공부한 것에 대한 효용감을 느끼게 해준 문제이다. 문제 설명을 보고 전기용품과 페이지가 대응되었고, 곧바로 페이징 알고리즘 중 OPT 알고리즘을 적용하면 됨을 깨달았다.

그러나 코딩 테스트 준비 차원에서 인터넷 검색을 하고 있지 않기 때문에 기억이 가물가물해서 실수를 했다. 처음 내가 기억하고 있던 방식은 앞으로 사용될 횟수가 가장 적은 요소를 선택하는 것이었다. 그렇게 첫 번째 제출한 답은 틀렸다. OPT 페이징 알고리즘은 앞으로 가장 오랫동안 사용되지 않을 요소를 선택하는 것이다.

/**
 * @file 1700_Greedy.cpp
 * @brief 00:46:48
 * @date 2024-07-05
 * 
 * @copyright Copyright (c) 2024
 * 
 */
#include <bits/stdc++.h>
using namespace std;

int N, K, cnt;
vector<int> seq;
vector<bool> plug;
vector<queue<int>> nextidx;

inline int FindCandidate();

int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> K;
    seq.resize(K);
    plug.resize(K + 1, false);
    nextidx.resize(K + 1);
    
    for (int i = 0; i < K; i++) {
        cin >> seq[i];
        nextidx[seq[i]].push(i);
    }

    int i = 0;
    while (N > 0 && i < K) {
        if (!plug[seq[i]]) {
            plug[seq[i]] = true;
            N--;
        }
        nextidx[seq[i]].pop();
        i++;
    }

    while (i < K) {
        nextidx[seq[i]].pop();
        if (!plug[seq[i]]) {
            cnt++;
            int victim = FindCandidate();
            plug[victim] = false;
            plug[seq[i]] = true;
        }
        i++;
    }

    cout << cnt;

    return 0;
}

inline int FindCandidate() {
    int maxv = 0, victim = -1;
    for (int i = 1; i <= K; i++)
        if (plug[i]) {
            if (!nextidx[i].size())
                return i;

            if (maxv < nextidx[i].front()) {
                maxv = nextidx[i].front();
                victim = i;
            }
        }

    return victim;
}

FindCandidate()의 시간복잡도가 O(K)이고 해당 함수를 사용하는 루프의 시간복잡도가 O(K)이므로, 이 코드의 시간복잡도는 O(K^2)이다.

내 답안은 다른 답안들에 비해 10% 정도의 메모리를 더 사용하였다. 일단 plug는 현재 끼워져 있는 플러그를 나타내기 위한 배열이고, N개의 플러그를 채울 때까진 플러그를 끼우는 동작만 수행하였다.

N개의 플러그를 채운 이후엔 현재 전기용품이 멀티탭에 끼워져 있지 않을 경우 FindCandidate()로 OPT 알고리즘을 사용해 다음에 뽑힐 플러그를 탐색하고, 해당 플러그와 현재 플러그를 교체한다.

OPT 알고리즘 구현을 위해 사용한 변수가 바로 nextidx이다. 이것은 큐를 원소로 갖는 벡터로, 인덱스는 전기용품의 ID를 의미한다. 처음 전기용품 ID의 시퀀스를 입력받을 때, nextidx에서 전기용품 ID 인덱스에 해당하는 큐에 시퀀스의 인덱스를 삽입한다.

예제 입력을 갖고 nextidx를 구성하면 다음과 같다.

• nextidx[1]: 4
• nextidx[2]: 0 -> 2 -> 5
• nextidx[3]: 1 -> 3
• nextidx[4]:
• nextidx[5]:
• nextidx[6]:
• nextidx[7]: 6

FindCandidate()가 호출되면, 현재 멀티탭에 끼워져 있는 전기용품들의 다음 인덱스를 찾는다. nextidx를 잘 관리해야 nextidx[i].front()가 다음 인덱스를 나타내게 할 수 있다. 그래서 입력 시퀀스를 탐색할 때 nextidx[seq[i]].pop()과 같이 seq[i](= 전기용품 ID)의 현재 인덱스를 큐에서 계속 제거해 나가는 것이다.

큐가 비어 있으면 앞으로 참조될 일이 없다는 것이므로 아무 원소나 반환하면 된다. 모든 큐에 원소가 하나 이상 있으면(즉, 현재 멀티탭에 끼워져 있는 전기용품이 미래에 한 번이라도 참조될 수 있으면) 큐의 맨 앞 원소(다음에 참조될 인덱스)가 최대인 것을 골라 해당 원소의 전기용품 ID를 반환한다.

제출 후 확인해보니 solved.ac에서 골드 1 난이도로 평가되어 있던데, 이렇게 잘 알려진 알고리즘이 골드 1로 평가받을 정도면 운영체제를 학습하지 않은 사람에겐 플래티넘 문제로 느껴질 것 같다.