[백준 1700] 멀티탭 스케줄링 - JAVA

문제

기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다.
준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등
여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다.

그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고,
이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다.

예를 들어
3 구(구멍이 세 개 달린) 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 같이 주어진다면,

1. 키보드
2. 헤어드라이기
3. 핸드폰 충전기
4. 디지털 카메라 충전기
5. 키보드
6. 헤어드라이기
7. 키보드, 헤어드라이기, 핸드폰 충전기의 플러그를 순서대로 멀티탭에 꽂은 다음 디지털 카메라 충전기 플러그를 꽂기 전에 핸드폰충전기 플러그를 빼는 것이 최적일 것이므로 플러그는 한 번만 빼면 된다.

입력

첫 줄에는 멀티탭 구멍의 개수 $N (1 ≤ N ≤ 100)$과 전기 용품의 총 사용횟수 $K (1 ≤ K ≤ 100)$가 정수로 주어진다.
두 번째 줄에는 전기용품의 이름이 $K$ 이하의 자연수로 사용 순서대로 주어진다.
각 줄의 모든 정수 사이는 공백문자로 구분되어 있다.

출력

하나씩 플러그를 빼는 최소의 횟수를 출력하시오.

---

접근 방법

우선 구멍에 플러그들을 모두 꼽고 하나의 플러그씩 교체해야하는 것을 인지하고 이 문제가 그리디 문제인 것을 인지했습니다.

그리고 $N$과 $K$의 범위도 매우 좁기 때문에 단순 구현으로도 어렵지 않게 구현할 수 있을 것이라 생각했습니다.

우선 플로우는 다음과 같습니다.

• 우선 비어있는 콘센트 구멍에 차례대로 플러그를 꼽습니다.
• 빈 구멍이 없는 경우 다음과 같은 방법으로 하나를 교체합니다.
  • 다음 사용할 전자용품이 현재 구멍에 꼽혀있지 않은 경우
    • 현재 플러그가 꼽혀있는 전자용품 중 가장 나중에 다시 사용하는 전자용품을 다음 전자용품과 교체한다
  • 다음 사용할 전자용품이 현재 구멍에 꼽혀있는 경우
    • 그대로 둔다

구현이 단순하기 때문에 단순한 $for$문으로도 풀 수 있었지만
$N$과 $K$의 범위가 늘어났을 때를 가장하고 최적화를 시도했습니다.

우선 첫 $for$문 순회를 통해
order라는 배열에 순서를 기록하고
Map에 모든 전자용품의 사용 시기와 현재 인덱스를 저장합니다.

그 다음 순회 때 order 배열을 다시 순회하면서
현재 콘센트에 꼽혀있는 전자용품을 set에 저장하고
해당 전자용품의 다음 사용 시기를 PriorityQueue에 저장합니다. (PriorityQueue = $pq$)

만약 다음 전자용품이 이미 콘센트에 꼽혀있다면
$pq$에 해당 전자용품의 다음 출현 시기를 추가하고
꼽혀있지 않다면 교체 로직을 수행합니다.

1. $pq$에서 $poll()$을 하는데 현재 플러그가 꼽혀있는 전자용품이 나올 때까지 반복
2. 현재 플러그가 꼽혀있는 전자용품 = 현재 플러그가 꼽혀있는 전자용품 이므로 해당 전자용품을 set에서 제거
3. 다음 전자용품을 $set$에 추가, $pq$와 $map$에 갱신 및 카운트 증가

이렇게 구현을 하게 되면 $\mathbf{O(K \log N)}$의 시간 복잡도로 문제를 해결할 수 있습니다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class PlugInfo {
    int index;
    List<Integer> memo;

    public PlugInfo (int index, List<Integer> memo) {
        this.index = index;
        this.memo = memo;
    }
}

class PluggedItem implements Comparable<PluggedItem> {
    String name;
    int index;

    public PluggedItem (String name, int index) {
        this.name = name;
        this.index = index;
    }

    @Override
    public int compareTo(PluggedItem o) {
        return Integer.compare(o.index, this.index);
    }
}

public class Main {
    static StringTokenizer st;
    static int N;
    static int K;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        if (N >= K) {
            System.out.println(0);
        }
        else {
            st = new StringTokenizer(br.readLine());
            Map<String, PlugInfo> map = new HashMap<>();
            String[] order = new String[K];

            for (int i = 0; i < K; i++) {
                String name = st.nextToken();
                order[i] = name;
                PlugInfo plugInfo;

                if (!map.containsKey(name))
                    plugInfo = new PlugInfo(0, new ArrayList<>());
                else
                    plugInfo = map.get(name);

                plugInfo.memo.add(i);
                map.put(name, plugInfo);
            }

            Set<String> holes = new HashSet<>();
            PriorityQueue<PluggedItem> pq = new PriorityQueue<>();
            int count = 0;

            for (String name : order) {
                if (holes.contains(name)) {
                    pq.offer(new PluggedItem(name, findNextIndex(map, name)));
                    continue;
                }

                if (holes.size() < N) {
                    holes.add(name);
                    pq.offer(new PluggedItem(name, findNextIndex(map, name)));
                }
                else {
                    if (!holes.contains(name)) {
                        while (true) {
                            PluggedItem pluggedItem = pq.poll();

                            if (holes.contains(pluggedItem.name)) {
                                holes.remove(pluggedItem.name);
                                break;
                            }
                        }
                    }
                    count++;
                    holes.add(name);
                    pq.offer(new PluggedItem(name, findNextIndex(map, name)));
                }
            }
            System.out.println(count);
        }
    }

    private static int findNextIndex(Map<String,PlugInfo> map, String name) {
        PlugInfo plugInfo = map.get(name);

        int nextPointer = plugInfo.index + 1;
        plugInfo.index = nextPointer;

        map.put(name, plugInfo);

        if (nextPointer >= plugInfo.memo.size()) {
            return K;
        }

        return plugInfo.memo.get(nextPointer);
    }
}