1. 문제 설명 📌

최소한으로 플러그 빼는 횟수 세라! (다시 꽂는 횟수는 세지 마라!)

2. 접근 방식 🗃️

KEY WORD: GREEDY ALGORITHM

(0) 사전 세팅: 멀티탭을 나타내는 SET, 각 전자 기기의 현재 조회 중인 위치 기준 가장 가까운 index를 나타내는 QUEUE[전자기기 번호], 명령 순서를 나태는 ORDER[]를 미리 구현해둔다.

(1) QUEUE[] 채우기: 앞서 말했다시피, index는 각 기기의 번호이고, 배열마다 자신만의 큐를 가지고 있다. 큐에는 해당 index 번호 기기가 나온 index를 만날 때마나 삽입한다. 이렇게 되면, 큐의 front에는 가장 처음 조우한 index가 적혀 있을 것이다.

(2) SET(멀티탭) 채우기: 멀티탭을 나타내는 SET을 채운다. 0부터 N까지 진행하고, 만나는 값을 집어넣는다. SET을 사용한 이유는 범위 내 중복된 값이 있을 경우, 자동으로 중복 제거를 해주기 때문이다.

(3) ORDER [] 진행: SET의 마지막 삽입 값 이후 부터 ORDER의 내용을 시작한다. 현재 조회 중인 ORDER[i]를 now라 할 때 다음 경우의 수를 만날 수 있다.

(가) 멀티탭이 비어 있는데, now가 이미 꽂힌 전자 기기 번호 일 때 : 넘어간다.
(나) 멀티탭이 비어 있는데, now가 꽂혀있지 않는 전자 기기 번호 일 때: 꽂아 넣는다. set.add()
(다) 멀티탭이 가득 차 있고, 멀티탭에 이미 꽂힌 전자 기기 번호 일 때: 넘어간다.
(라) 멀티탭이 가득 차 있으나, 멀티탭에 꽂혀 있지 않은 번호 일 때:

마지막 경우의 수가 제일 중요하다. 이때는 멀티탭에 꽂혀 있는 전자 기기 중, 가장 먼저 다시 만나는 index가 제일 먼 값을 뽑아버리면 된다. 만약 멀티탭에 꽂혀 있는 전자 기기 중 다음으로 다시 만나는 index가 없는 경우, 다음부터 쓸 일이 없다는 것임으로, 그 값을 우선적으로 뽑아 처리해야 한다.

(1) 꽂혀있는 번호 중에서 가장 먼저 다시 만나는 index 중 제일 먼 값을 뽑는 이유

먼저 index 중 제일 먼 값을 뽑는 이유를 보자.

그림과 같이 현재 꽂혀 있는 기기의 번호가 2 3이고, 현재 그 외의 숫자를 만나서 둘 중 하나를 뺴야 한다고 가정했을 때, 2의 다음 index는 5이고, 3의 다음 index는 10이다.

현 시점에서 2를 조우한 K로 바꾸면, index = 5에서 2로 또 바꿔줘야 하고(K를 다시 바꾸든, 3을 바꾸든), 만약 3을 2로 바꿨다면, index = 10에서 다시 둘 중 하나를 3으로 바꿔야 한다.
최소 한번 최대 2번을 바꿔줘야 한다. 반면 꽂혀 있는 값 중 다음 index가 가장 먼 3을 K로 바꿔준다면,

index = 5에서 2를 조우할 때, 이미 꽂혀 있으므로 넘어가고, index = 10에서 다시 바꿔주면 된다. 그러니까 최대 1번만 바꿔주면 되는 것이다. 이처럼 꽂혀 있는 값 중 다음으로 만나는 번호가 먼 값을 뽑아버리는 게 이득이다.

두 번째로 꽂혀 있는 값의 index 중 가장 먼저 만나는 값을 비교 대상으로 삼는 이유를 보자.

3 14

1 4 3 2 5 4 3 2 5 3 4 2 3 4

콘셉트 구멍이 3개이므로 초기에 꽂힌 기기의 번호는 [1,4,3]일 것이다. 만약에 위의 예시 입력을 계산할 때, 꽂혀 있는 값 중 가장 먼저 만나는 index가 아닌, 전체 index 중 제일 먼 값으로 계산 시 4가 항상 제외 되게 된다. 하지만 4의 제일 앞 index는 5로 3보다 먼저 나오는 경우가 있다. 따라서 그렇게 계산하면, 불필요한 콘셉트 뽑기가 +1 더 들어가게 된다.

이처럼, 전체에서 맨 뒤 index에 위치한다고 해서, 최적의 해를 구하지 못하는 반례가 있으므로, 제일 가까운 index 중 제일 먼 기기를 뽑아 버려야 한다.

3. 코드 소개 🔎

import java.io.*;
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
    public static void main(String[] args) throws IOException {
        int answer = 0;
        int N, K;
        int [] orders;
        Queue<Integer> [] indexes = new Queue[101];
        HashSet<Integer> concept = new HashSet<>();

        for (int i = 1; i < 101; i++) {
            indexes[i] = new ArrayDeque();
        }

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        orders = new int [K];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < K; i++) {
              orders[i] = Integer.parseInt(st.nextToken());
              if(i < N) concept.add(orders[i]);
              else {indexes[orders[i]].add(i);}
        }

        for (int i = N; i < K; i++) {
            int now = orders[i];
            indexes[now].poll();

            if(concept.contains(now)) continue;
            if(concept.size() < N) {
                concept.add(now);
                continue;
            }

            int latest_v = 0;
            int latest_i = 0;
            for (int plug_in : concept){

                if(indexes[plug_in].peek() == null) {
                    latest_v = plug_in;
                    break;
                }

                if(!indexes[plug_in].isEmpty() && indexes[plug_in].peek() > latest_i){
                    latest_i = indexes[plug_in].peek();
                    latest_v = plug_in;
                }
            }
            concept.remove(latest_v);
            concept.add(now);
            answer++;
        }
        System.out.println(answer);
    }
}