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

문제

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

20136번: 멀티탭 스케줄링 2

---

알고리즘

그리디 알고리즘, 우선순위 큐

 

일단 기본적으로 문제 해결방법은 아래 "멀티탭 스케줄링" 1탄을 보고 와주길 바란다. 멀티탭 스케줄링 2는 1을 어떻게 더 효율적으로 해결할 수 있을지를 고민하면 되는 문제기 때문에 이에 대해서만 다룰 것이다.

 

https://mclub4.tistory.com/3

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

 

기존에 멀티탭 스케줄링 1탄에서는 "꽂혀있는 것들이 바로 다음에 언제 나오는가?"를 알아내기 위해서 브루트포스적으로 반복문을 돌렸다. 하지만, 해당 문제는 n이 100으로 작아서 시간초과가 나지 않고 가능했던 것이다. 하지만, 멀티탭 스케줄링 2 문제는 n이 50만이다. 따라서, 기존 방법으로 하면 무조건 시간초과가 나기 때문에 이 바로 다음에 언제 나오는가를 효율적으로 구현할 방법을 찾아야한다.

 

이를 위해서, 우선순위 큐를 이용할 것이다. 우선, 각 전자기기가 언제언제 나오는지를 기록하기 위해 각 전자기기 별 사용 시점들을 기록할 Queue를 만들어 주었다. 쉽게 꺼내기 위해서 queue를 사용한 것이지만, arraylist를 사용하고 사용할때마다 제거해줘도 상관은 없다. 그리고, 입력을 받을때 이 시점을 큐에 넣어준다.

 

그 다음, 이제 멀티탭에 꽂혀있는 것들을 기록하기 위해 멀티탭을 우선순위 큐로 만들 것이다. 멀티탭에는 {전자기기 번호, 꽂은 시점을 기준으로 바로 다음에 나오는 시점}으로 들어가 있으며, 바로 다음에 나오는 시점을 기준으로 내림차순 정렬되도록 해놨다. 이렇게 하면, 굳이 브루트포스적으로 반복문 돌려가면서 바로 다음에 나오는 시점을 구할 필요가 없이 제일 앞에 원소를 뽑아 쓰면 된다. 예시를 들어보겠다.

 

2 3 2 3 1 2 7

이렇게 들어왔다고 가정해보자. 그럼 각 전자기기의 순서 큐에는 (순서는 1부터 시작한다고 가정함)

1: 5

2: 1 3 6

3 : 2 4

4,5,6 : X

7 : 7

이렇게 들어가 있을 것이다.

 

그럼 멀티탭 우선순위 큐에 들어가는걸 차례로 적어보면 (이때, 더이상 바로 다음에 나오는 경우가 없으면 무한대로 넣는다고 가정해보자)

첫번째 : {2,3}

두번째 : {3,4} , {2,3}

세번째 : {2,6}, {3,4}, {2,3}

네번째 : {3, INF}, {2,6}, {3,4}, {2,3}

까지 온다음에 이제 5번째를 주의깊게 봐보자. 바로 다음에 나오는 순서를 기준으로 내림차순 정렬했으므로 제일 앞에 원소 3을 뽑으면 된다. 그리고 1을 추가해준다.

 

다섯번째 : {1,INF}, {2,6}, {3,4}, {2,3}

여섯번째 : {1,INF}, {2,INF},  {2,6}, {3,4}, {2,3}

일곱번째 : {2,INF}, {7,INF}, {2,6}, {3,4}, {2,3}

이렇게 끝이 난다. 다섯번째를 꽂을때와 일곱번째를 꽂을때 각각 3과 1을 뽑았으므로 플러그를 빼는 최소 횟수는 2회가 된다. 이렇게 우선순위 큐를 이용하여 굳이 브루트포스적으로 반복문을 돌려가며 탐색하지 않도록 만들었고, 이로 인하여 시간내에 돌아가게 된다.

---

코드

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];

        //각 전자기기 별로 큐를 만들어줌. 각 전자기기가 몇번째 오는지 기록용도
        Queue<Integer> queue[] = new LinkedList[k+1];
        for (int i = 0; i < k+1; i++) {
            queue[i] = new LinkedList<>();
        }

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

        for(int i = 1; i<k+1; i++){
            electronic[i] = Integer.parseInt(st.nextToken());
            //각 전자기기가 몇번째에 오는지 기록
            queue[electronic[i]].add(i);
        }

        //멀티탭에 꽂혀 있는 것들 기록. 이때, {전자기기 번호, 현재시점을 기준으로 다음에 오는 순서}로 저장됨.
        //또한, multiptap은 현재시점을 기준으로 다음에 오는 순서로 정렬됨.
        PriorityQueue<int[]> multitap = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[1] - o1[1];
            }
        });
        //이미 꽂혀있는 전자기기 표시
        boolean[] use = new boolean[k+1];
        //멀티탭을 뽑은 횟수
        int count = 0;
        //현재 멀티탭에 꽂혀있는 전자기기 개수
        int now = 0;

        for(int i = 1; i<k+1; i++){
            int cur = electronic[i];
            //이미 꽂혀있을 경우
            if(use[cur]){
                //해당번째의 전자기기 순서는 패스
                queue[cur].poll();
                //해당 전자기기가 현재 시점을 기준으로 다시는 오지 않는다면, 나중에 오는 순서는 무한대로 기록
                if(queue[cur].isEmpty()) multitap.add(new int[]{cur, Integer.MAX_VALUE});
                //현재 시점을 기준으로 다음에 오는 경우가 있다면, 그 순서를 기록
                else multitap.add(new int[]{cur, queue[cur].peek()});
            }
            //현재 멀티탭에 공간이 있다면 그냥 꽂으면 된다.
            else if(now < n){
                //해당 전자기기를 사용중이라고 기록을 해주고
                use[cur] = true;
                //해당번째 전자기기 순서를 없에주고
                queue[cur].poll();
                //현재 멀티탭에 꽂혀있는 개수를 늘려줌
                now ++;
                //해당 전자기기가 현재 시점을 기준으로 다시는 오지 않는다면, 나중에 오는 순서는 무한대로 기록
                if(queue[cur].isEmpty()) multitap.add(new int[]{cur, Integer.MAX_VALUE});
                //현재 시점을 기준으로 다음에 오는 경우가 있다면, 그 순서를 기록
                else multitap.add(new int[]{cur, queue[cur].peek()});
            }
            //멀티탭에 공간이 없는데 새로운 전자기기가 들어오는 경우
            else{
                //멀티탭에 꽂혀있는 것 중에서 현재 시점을 기준으로 바로 다음에 오는 순서가 가장 늦은 것을 뽑을 것임
                //multitap은 순서를 기준으로 정렬했으므로 제일 앞에 전자기기 번호를 받아옴.
                int out = multitap.peek()[0];
                //그리고 멀티탭에서 제거
                multitap.poll();
                //해당 전자기기 사용 표시를 없에줌
                use[out] = false;
                //해당 전자기기의 순서도 제거
                queue[cur].poll();
                //새로운 전자기기가 현재 시점을 기준으로 다시는 오지 않는다면, 나중에 오는 순서는 무한대로 기록
                if(queue[cur].isEmpty()) multitap.add(new int[]{cur, Integer.MAX_VALUE});
                //현재 시점을 기준으로 다음에 오는 경우가 있다면, 그 순서를 기록
                else multitap.add(new int[]{cur, queue[cur].peek()});
                use[cur] = true;
                //멀티탭 뽑은 횟수 증가
                count ++;
            }
        }

        System.out.println(count);
    }
}