문제

아이디어

문제의 이름과 설명을 보았을 때, 운영 체제의 페이지 교체 알고리즘을 연상케한다.
전기용품을 페이지로 치환한다면 페이지 폴트를 최소화하는 문제로 바꿀 수 있겠다.
다행히도 우리는 페이지 폴트를 최소화하는 최적 알고리즘을 알고 있으니 적용한다면 쉽게 풀어낼 수 있다.

최적 알고리즘에 대해서 간단히 설명하자면, 가장 오랫동안 쓰지 않을 페이지를 교체 대상으로 한다.
이후에 사용할 프로세스의 순서를 모두 알고 있어야 하므로 OS가 실제로 스케줄링할 때 사용하지는 못한다.

소스코드

import java.io.*;
import java.util.*;

public class Main {
    static int N, K;
    static int[] works;
    static Set<Integer> multi;

    static int getOptPlug(int t) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int plug : multi) {
            map.put(plug, Integer.MAX_VALUE);
        }

        for (int i = t; i < K; i++) {
            if (multi.contains(works[i]))
                map.put(works[i], Math.min(map.get(works[i]), i));
        }

        int ret = 0, maxT = 0;
        for (Integer i : map.keySet()) {
            if(map.get(i) > maxT){
                ret = i;
                maxT = map.get(i);
            }
        }
        return ret;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        multi = new HashSet<>();
        works = new int[K];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < K; i++) {
            works[i] = Integer.parseInt(st.nextToken());
        }

        int ans = 0;
        for (int i = 0; i < K; i++) {
            if (multi.contains(works[i]))
                continue;
            else if (multi.size() == N) {
                multi.remove(getOptPlug(i));
                ans++;
            }
            multi.add(works[i]);
        }

        System.out.println(ans);
    }
}

채점결과

골드 1 문제치고는 간단하게 풀렸다.
아무래도 운영체제에 대한 기본 지식을 요구하므로 실제 난이도보다 높게 측정된 것 같다.
입력값의 범위도 좁은 편이니 어떻게든 최적 알고리즘을 구현할 수 있다면 쉽게 풀 수 있겠다.