[백준] 1700 - 멀티탭 스케쥴링(Java)

문제 파악

https://www.acmicpc.net/problem/1700

 

풀이

사용 순서를 순환하며 멀티탭에 자리가 없다면, 현재까지 꽂은 플러그 중 하나를 뽑아 제거해 준다.
이 때, 제거할 플러그는 이 후의 사용 순서를 고려해 주어야 한다.

앞으로의 사용순서를 어떻게 사용하는 게 좋을까 😊

 

빈도수가 높은 플러그를 멀티탭에 꽂아놓는게 어떨까 싶은 생각이 들었다.. 아쉽게도 틀린 접근👹이다.
앞으로의 등장 빈도가 높아도, 사용 시점이 너무 늦다면 멀티탭의 자리만 차지하는 꼴이므로 교체 빈도가 높아진다.
뿐만 아니라 빈도수가 같은 경우가 발생하면 우선순위를 적용하기 어렵다.

1 - 2 - 3 - 1 - 4 - 1 - 2 - 2 - 2 의 경우 

앞으로 잘 안 쓸 플러그를 뽑게 된다면

1(1) - 2(1,2) - 3(1,2,3) - 1(2,3,1) - 4(1,2,4) - 1(4,1,2) - 2(1,2) - 2(1,2) - 2(1,2)
총 4번을 교체한다

 

해결책은 멀티탭에 꽂힌 플러그 중 앞으로 가장 늦게 등장하는 플러그를 제거해주면 문제를 해결할 수 있다.

1(1) - 2(1,2) - 3(2,1,3) - 1(1,3) - 4(3,1,4) - 1(1,4) - 2(1,2,4) - 2(2,4) - 2(2,4)

총 3번을 교체한다.

 

구현

자체는 이차원 배열로 단순하게 진행했다.

pos[plug][position]을 선언하여,
position 위치 이후로 등장하는 plug의 가장 가까운 위치를 저장해 주도록 한다.

k-1 -> 0으로 역순으로 돌며 해당 이차원 배열을 초기화 해준 후

멀티탭에 플러그를 꽂아야 하는데, 자리가 없는 경우 이차원 배열을 참고하여 가장 멀리 있는 플러그를 제거해준다.

 

코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.Arrays;  
import java.util.HashSet;  
import java.util.Set;  
import java.util.StringTokenizer;  
  
public class Main {  
    private static int[] order;  
    private static int n, k;  
    private static int[][] pos;  
    private static Set<Integer> plugs;  
  
    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());  

		plugs = new HashSet<>(n);  
        order = new int[k];  
        
        st = new StringTokenizer(br.readLine(), " ");  
        for (int i = 0; i < k; i++) {  
            order[i] = Integer.parseInt(st.nextToken());  
        }        int answer = 0;  
        
        // initialize : pos[plug][idx]  
        int[] plugPosition = new int[k + 1];
        pos = new int[k + 1][k];  
        Arrays.fill(plugPosition, Integer.MAX_VALUE);  
        for (int i = k - 1; i >= 0; i--) {  
            int o = order[i];  
            plugPosition[o] = i;  
            for (int kk = 1; kk <= k; kk++) {  
                pos[kk][i] = plugPosition[kk];  
            }
        }
  
        for (int i = 0; i < k; i++) {  
            if (plugs.contains(order[i])) {  
                continue;  
            }  
            if (plugs.size() >= n) {  
                int eliminate = plugToEliminate(i);  
                plugs.remove(eliminate);  
                answer++;  
            }  
            plugs.add(order[i]);  
        }
        System.out.println(answer);  
    }  
  
  
    private static int plugToEliminate(int currIdx) {  
        int farthestPlug = 0;  
        int farthestDist = -1;  
        for (int p : plugs) {  
            if (farthestDist < pos[p][currIdx]) {  
                farthestPlug = p;  
                farthestDist = pos[p][currIdx];  
            }  
        }  
        return farthestPlug;  
    }  
}