[Algorithm/Java][백준] 1700번 멀티탭 스케줄링

[BOJ] 1700번 멀티탭 스케줄링

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

문제 접근

예전에 운영체제 시간에 배웠던 페이지 교체 알고리즘과 비슷해서 쉽게 풀 수 있었다.
멀티탭에 자리가 있거나, 이미 꽂혀있을 때는 고려할 것 없이 그냥 꽂거나 넘어가면 되지만 자리가 없을때 고려해야 될 경우의 수가 있다.
경우의 수를 정리해 보면 다음과 같다.

1. 멀티탭에 자리가 있는 경우
2. 이미 멀티탭에 꽂혀 있는 경우
3. 멀티탭에 자리가 없는 경우
   3.1. 사용하지 않을 전자기기가 꽂혀 있는 경우
   3.2. 모든 전자기기가 다시 사용할 전자기기인 경우

사용하지 않을 전자기기가 꽂혀 있으면 그 전자기기를 제거하고 새로운 전자기기를 꽂으면 해결된다.
모든 전자기기가 다시 사용할 전자기기인 경우 우선순위를 두어서 가장 낮은 것을 제거해 주면 된다.
먼저 사용해야 하는 전자기기의 우선순위를 높게 설정해서 가장 나중에 사용할 전자기기를 제거해 주는 방식으로 해결하였다.

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ1700 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        List<Integer> orders = new ArrayList<>();
        List<Integer> multitap = new ArrayList<>();
        int answer = 0;
        for(int i = 0; i<k; i++){
            orders.add(Integer.parseInt(st.nextToken()));
        }
        while(!orders.isEmpty()){
            int order = orders.remove(0);
            // 멀티탭에서 이미 사용중인 경우
            if(multitap.contains(order)) continue;
            // 멀티탭에 자리가 있는 경우
            if(multitap.size() < n){
                multitap.add(order);
            } else {
            // 멀티탭에 자리가 없는 경우
                boolean flag = false;
                int idx = -1;
                int maxIdx = -1;
                answer++;
                for(int i = 0; i<multitap.size(); i++){
                    if(!orders.contains(multitap.get(i))){
                        // 다시 사용하지 않을 전자기기인 경우
                        flag = true;
                        multitap.remove(i);
                        multitap.add(order);
                        break;
                    } else {
                        if(orders.indexOf(multitap.get(i))> idx){
                        // 다시 사용할 전자기기의 우선순위를 계산
                            idx = orders.indexOf(multitap.get(i));
                            maxIdx = i;
                        }
                    }
                }
                if(!flag){
                    // 모든 전자기기가 다시 사용할 전자기기인 경우
                    // 계산한 우선순위를 이용해서 해결
                    multitap.remove(maxIdx);
                    multitap.add(order);
                }
            }
        }
        System.out.println(answer);
    }
}