[백준] 멀티탭 스케줄링 (그리디)

문제 소개

멀티탭 스케줄링 - 백준 1700번 문제를 정리합니다.
이 문제는 멀티탭에 꽂을 수 있는 전기용품 수가 제한된 상황에서, 최소 횟수로 플러그를 뽑는 그리디 스케줄링 문제입니다.
핵심은 "멀티탭에 꽂혀 있는 전기용품 중 어떤 걸 뽑을지"를 먼저 고민해야합니다.

문제 링크: 멀티탭 스케줄링 - 백준 1700번

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 전기용품이 이미 꽂혀 있다면 그대로 사용
2. 빈 자리가 있다면 꽂음
3. 빈 자리가 없다면, 이후 사용 계획을 참고해 가장 늦게 사용하거나 더 이상 사용하지 않을 전기용품을 뽑음
4. 위 과정을 반복하며 플러그 교체 횟수를 계산

---

해결 과정 및 코드

핵심 아이디어

1. 현재 꽂혀 있는 전기용품들을 used 배열로 관리
2. 매 순간 꽂으려는 전기용품이 이미 사용 중이면 패스
3. 아니라면 이후 사용 순서를 탐색하여 앞으로 사용할 전기용품들을 우선순위로 뽑음
   • 만약 이후에도 계속 쓰일 전기용품이 있다면, 가장 나중에 등장하는 전기용품을 뽑음
   • 만약 쓰이지 않을 전기용품이 있다면 그걸 우선적으로 뽑음
4. 최적의 제거 대상 선정 후 새 전기용품을 꽂고, 뽑는 횟수 change++ 증가

코드

시간 복잡도 : O(K × N)
이유: 매 순간 최대 N개의 전기용품 중 제거 대상을 결정하기 위해, 남은 순서를 훑어야 하기 때문

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

public class Main {
    static int N, K, useOrder[], change = 0;
    static boolean[] used;

    public static void main(String[] args) throws Exception {
        N = read();  // 멀티탭 구멍 수
        K = read();  // 전체 사용 횟수
        useOrder = new int[K];
        used = new boolean[101]; // 전기용품 번호는 1~100

        for (int i = 0; i < K; i++) {
            useOrder[i] = read();
        }

        int cur = 0;

        // 초기 멀티탭 세팅
        for (int i = 0; i < K && N > 0; i++) {
            if (!used[useOrder[i]]) {
                used[useOrder[i]] = true;
                N--;
            }
            cur++;
        }

        for (; cur < K; cur++) {
            int device = useOrder[cur];

            if (used[device]) continue; // 이미 꽂혀있다면 넘어감

            // 현재 멀티탭에 꽂혀 있는 기기 중, 앞으로 가장 늦게 쓰이거나 안 쓰일 기기 제거
            ArrayList<Integer> useList = new ArrayList<>();
            for (int i = cur; i < K; i++) {
                int d = useOrder[i];
                if (used[d] && !useList.contains(d)) {
                    useList.add(d);
                }
            }

            // 앞으로 안 쓰일 기기 제거
            if (useList.size() < N) {
                for (int i = 1; i <= 100; i++) {
                    if (used[i] && !useList.contains(i)) {
                        used[i] = false;
                        break;
                    }
                }
            } else {
                // 가장 나중에 쓰일 기기 제거
                int remove = useList.get(useList.size() - 1);
                used[remove] = false;
            }

            used[device] = true; // 새 기기 꽂음
            change++; // 플러그 뺀 횟수 증가
        }

        System.out.println(change);
    }

    // 빠른 입력
    private static int read() throws Exception {
        int n = 0, c;
        while ((c = System.in.read()) > 32)
            n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }
}

참고할 주요 개념

이 문제를 풀면서 알아두면 좋은 개념은 캐시 교체 알고리즘의 OPT(Optimal Page Replacement)입니다.

✅ OPT (Optimal Page Replacement)란?

• 앞으로 가장 오랫동안 사용되지 않을 페이지(또는 아이템)를 제거하는 전략
• 캐시 미스가 발생했을 때, 앞으로 가장 나중에 사용되거나 아예 다시 사용되지 않을 페이지를 제거하는 것이 이론적으로 가장 최적
• 단, 미래의 사용 순서를 알아야 하므로 실제 시스템에서 구현은 불가능하지만, 이론적 최적 기준으로 자주 사용됨
• 페이지 교체 문제, CPU 캐시, 가상 메모리 관리 등에서 비교 기준으로 사용됨

✅ 멀티탭 스케줄링 문제와의 연결

멀티탭 문제에서도 동일한 전략을 사용:

• 현재 멀티탭에 꽂혀 있는 전기용품들 중,
• 앞으로 가장 늦게 다시 사용되거나 아예 다시 사용되지 않을 전기용품을 제거하는 것이 최적
• 즉, OPT 캐시 교체 알고리즘을 그대로 시뮬레이션하는 문제라고 볼 수 있음