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

문제

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

1700번: 멀티탭 스케줄링

 

입력

 

출력

---

알고리즘

그리디 알고리즘

 

회의실 배정 문제와 유사하다. 멀티탭을 뽑는 횟수를 가장 최소화 할려면 현재 멀티탭에 꽂혀있는 것 중에서 가장 나중에 나오는 것을 뽑으면 된다. 예시로 멀티탭 구멍 개수가 2개이고 7개의 전자제품을 아래와 같이 사용한다면

2 3 2 3 1 2 7

 

우선, 처음에 나오는 2와 3은 멀티탭이 비어 있으므로 그냥 바로 꽂는다. 그 다음에 나오는 2와 3은 이미 멀티탭에 꽂혀 있으므로 굳이 뺄 필요가 없다. 이제 다섯번째로 나오는 1이 문제인데, 앞서 말했다 싶이 현재 꽂혀있는 것 중에서 가장 나중에 나오는 것을 구한다. 1을 꽂으려는 시점에서는 2와 3이 꽂혀있다. 그럼 이 두개가 바로 다음에 언제 나오는지 확인한다. 2는 여섯번째 나오고, 3은 더이상 나오지 않는다. 나오지 않는 경우를 무한대라고 생각한다면, 더 나중에 나오는 것은 3이다. 따라서, 3을 뽑고 1을 꽂으면 된다. 이어서, 여섯번째 2는 이미 꽂혀있으니깐 패스하고 마지막 7을 꽂는 상황을 보자. 7을 꽂는 시점에 멀티탭에는 1과 2가 꼽혀있다. 이 두개가 바로 다음에 언제 나오는지 확인해보면 1과 2 둘다 더이상 나오지 않는다. 따라서, 둘다 무한대이므로 둘중 하나 아무거나 뽑으면 된다. 따라서, 멀티탭을 뽑는 최소 횟수는 2가 된다.

 

위를 염두해두고 3가지 경우를 나눠서 코드를 세우면 된다.

 

1. 멀티탭에 빈공간이 있을 경우 : 그냥 바로 멀티탭에 꽂으면 된다.

2. 이미 꽂혀있는 전자기기를 또 사용하려는 경우 : 굳이 뽑고 다시 꽂을 필요가 없으므로 스킵한다.

3. 멀티탭이 가득차 있는데 꽂혀있지 않은 전자기기를 사용하려는 경우 : 해당 전자기기를 사용하려는 시점에서, 멀티탭에 꽂혀있는 모든 전자기기가 바로 다음에 언제 나오는지 확인한다. 그 중에서 가장 나중에 나오는 전자기기를 뽑고 새로운 전자기기를 꽂는다. 이때, 중요한 것은 한참뒤에 나오는 시점 말고 "바로 다음" 나오는 시점을 가지고 비교해야 한다.

 

아래 코드는 3번 경우를 단순 반복문으로 구현했는데, n이 100으로 매우 작아서 시간초과가 나지 않는다. n이 클 경우는 반복문이 아닌 다른 방법으로 구현해야 한다. 20136 멀티탭 스케줄링 2가 이에 해당하는 문제이다. 해당 문제 풀이는 밑에 글 참조.

 

https://mclub4.tistory.com/5

[백준] 20136번 - 멀티탭 스케줄링 2 (Java)

---

코드

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

public class Main {
    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());

        int[] electronic = new int[k+1];

        st = new StringTokenizer(br.readLine());

        for(int i = 1; i<k+1; i++){
            electronic[i] = Integer.parseInt(st.nextToken());
        }

        ArrayList<Integer> list = new ArrayList<>();
        int count = 0;

        //멀티탭 뽑는 횟수를 가장 적게 할려면? 꼽혀있는 것 중에서 가장 나중에 나오는걸 뽑으면 된다.
        for(int i = 1; i<k+1; i++){
            // 1. 이미 꼽혀있는 전자기기를 또 꼽으려는 경우
            if(list.contains(electronic[i])) continue;
            // 2. 다른 전자기기를 꼽으려하는데, 멀티탭에 자리가 남아 있는 경우
            if(list.size() < n){
                list.add(electronic[i]);
                continue;
            }

            //queue에는 int[] 배열이 저장된다.
            //첫번째 인덱스에는 그 전자기기의 이름이 저장되며, 두번째 인덱스에는 그 전자기기가 몇번째 다음에 나오는지 저장해둔다.
            //그리고 전자기기가 나오는 순서를 내림차순으로 정렬하면 제일 처음 원소가 제일 나중에 나오는 전자기기를 의미한다.
            //사실 우선순위큐 안써도 그냥 Arrays.sort()돌려도 된다. 그냥 정렬하려고 쓴거기 때문에..
            PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o2[1] - o1[1];
                }
            });
            //현재 꼽혀있는 모든 전자기기를 이후에 언제 나오는지 저장한다.
            //n이 작기 때문에 브루트포스로 완전탐색 돌려도 시간초과가 나지 않는다.
            //만약에 n이 매우 크다면, 우선순위큐를 이용해서 완전탐색을 피해야한다.
            //백준 20136 멀티탭 스케쥴링2가 그런 문제이다. 추후 다룰 예정이다.
            for(int j = 0; j<list.size(); j++){
                int[] tmp = new int[2];
                tmp[0] = list.get(j);
                tmp[1] = 101;
                int idx = -1;
                //이후 시점 모두 완전 탐색하기
                for(int s = i+1; s<k+1; s++){
                    if(electronic[s] == tmp[0]){
                        idx = s;
                        break;
                    }
                }
                if(idx != -1) tmp[1] = idx;
                queue.add(tmp);
            }

            //제일 나중에 나오는건 멀티탭에서 뽑아버린다.
            list.remove(list.indexOf(queue.poll()[0]));
            //그리고 새로운 전자기기를 꼽아준다.
            list.add(electronic[i]);
            //멀티탭을 뽑은 횟수를 증가시킨다.
            count ++;
        }

        System.out.println(count);
    }
}