[Java][골드 1] 1700번 멀티탭 스케줄링

백준 1700 멀티탭 스케줄링

 

1. 문제 정리

멀티탭 구멍이 N개 있고, 전기용품을 사용하는 순서가 주어진다.

 

각 순서마다 해당 기기를 써야 하는데,

이미 꽂혀 있으면 그대로 쓰면 되고 없으면 꽂아야 한다.

 

근데 멀티탭이 꽉 차 있으면 하나를 뽑고 꽂아야 해서

이때 플러그를 뽑는 횟수를 최소로 만드는 문제다.

 

2. 풀이 전략

처음 보면 “덜 쓰는 걸 빼면 되나?” 또는 “최근에 안 쓴 걸 빼면 되나?” 같은 기준을 떠올리기 쉬운데,

이 문제는 그런 방식으로는 해결되지 않는다.

 

이 문제의 유형은 그리디 알고리즘이다.

단, 일반적인 그리디처럼 “현재 기준에서 가장 좋은 선택”이 아니라,

앞으로의 사용 순서를 기준으로 선택해야 전체 최적이 되는 형태다.

 

즉, 현재가 아니라 뒤까지 고려하는 것이 중요하다.

 

멀티탭이 꽉 찼을 때는 다음 기준으로 하나를 뽑는다.

1. 앞으로 다시 사용되지 않는 기기 → 바로 제거
2. 모두 다시 사용된다면 → 가장 나중에 다시 사용되는 기기 제거

 

이렇게 선택하는 이유는 다음과 같다.

• 다시 사용되지 않는 기기를 계속 유지할 이유가 없고
• 다시 사용해야 하는 경우라면, 가능한 한 늦게 사용할 기기를 제거해야 이후 교체 횟수를 최소화할 수 있기 때문이다

 

이 선택 기준이 매 순간 최적 선택이면서,전체 결과에서도 최적을 보장하기 때문에 그리디로 해결할 수 있다.

 

구현은 다음과 같은 흐름으로 진행된다.

• 이미 꽂혀 있는 기기라면 그대로 넘어가고
• 자리가 남아 있으면 바로 꽂는다
• 자리가 없다면 현재 꽂혀 있는 기기들을 하나씩 확인하면서
• “다음에 언제 다시 사용되는지”를 찾는다

 

그 다음,

• 이후에 전혀 등장하지 않는 기기가 있다면 그 기기를 선택하고
• 그렇지 않다면, 가장 늦게 다시 등장하는 기기를 선택하면 된다

 

이 과정을 순서대로 반복하면 된다.

 

 

3. 코드

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

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

        int n = Integer.parseInt(st.nextToken()); // 멀티탭 구멍 개수
        int m = Integer.parseInt(st.nextToken()); // 사용 순서 길이

        int[] num = new int[m];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) num[i] = Integer.parseInt(st.nextToken());

        List<Integer> list = new ArrayList<>(); // 현재 멀티탭에 꽂힌 기기
        int count = 0; // 플러그 뽑은 횟수

        for (int i = 0; i < m; i++) {

            // 이미 꽂혀 있으면 넘어감
            if (list.contains(num[i])) continue;

            // 자리가 남아 있으면 그냥 꽂기
            if (list.size() < n) {
                list.add(num[i]);
                continue;
            }

            // 뽑을 기기 선택
            int next = -1;       // 제거할 기기
            int farthest = -1;   // 가장 늦게 다시 사용되는 시점

            // 현재 꽂혀 있는 기기들 확인
            for (int s : list) {
                int idx = Integer.MAX_VALUE;

                // 이후에 언제 다시 등장하는지 찾기
                for (int j = i + 1; j < m; j++) {
                    if (s == num[j]) {
                        idx = j;
                        break;
                    }
                }

                // 다시 등장하지 않으면 바로 제거 대상
                if (idx == Integer.MAX_VALUE) {
                    next = s;
                    break;
                }

                // 가장 늦게 등장하는 기기 선택
                if (idx > farthest) {
                    farthest = idx;
                    next = s;
                }
            }

            // 선택된 기기 제거 후 현재 기기 삽입
            list.remove(Integer.valueOf(next));
            list.add(num[i]);
            count++;
        }

        System.out.println(count);
    }
}

 

 

4. 회고

 

이 문제는 생각보다 단순한 구현인데 아이디어를 못 떠올리면 아예 못 푸는 문제였다.

 

플러그가 다 차있는 상태에서 어떤 걸 뺄지 생각하는 것이 어려운 부분이였다.

 

결국 포인트는 지금 기준이 아니라, 앞으로 언제 쓰이냐를 기준으로 판단하는 것이었다.

 

그리디 문제를 풀 때 이 기준을 정확히 구현하는 것이 중요하다고 생각했다.