[Java] BaekJoon 1700. 멀티탭 스케줄링 (골드1) (그리디 알고리즘)

문제 출처: https://www.acmicpc.net/problem/1700

1700번: 멀티탭 스케줄링

 

문제이해

목표

구멍: N
전기용품 총 사용횟수: K

전기용품은 최대: K개 있 을 수 있다.

 

모든 전기용품의 사용 순서가 주어지고
모든 전기용품을 이용한다 했을 때 갈아낄 때 빼야하는 플러그의 횟수를 최소화 하시오 !

 

풀이

 

주어진 단서 정리

int[] intArr = new int[K + 1]; // 주어진 전기용품 순서. 1번째 부터 K번째 까지(주어진 입력 intArr)

ex) 2 3 2 3 1 2 7

 

Set<Integer> nowConcents = new HashSet<>(N);  // 콘센트 N개

 

priority = new ArrayList[K+1]; // 각 전기용품의 순서들을 담음

ex)

0: 
1: 5 
2: 1 3 6 
3: 2 4 
4: 
5: 
6: 
7: 7

 

해법

1. (intArr)한번의 탐색으로 priority에 전기용품의 순서들을 담는다. 

2. 다시 주어진 순서(intArr)을 탐색하는데 

-> 처음 콘센트 자리가 비어있거나, 콘센트 자리에 사용하려는 전기 용품이 이미 꽂혀있을때

   nowConcents에 값을 넣어 콘센트를 채우고, 해당 전기 용품의 가장 첫번째 순서를 지운다.

 

-> 위의 경우가 아니라면 콘센트 자리 하나를 비워줘야 된다.

    Set에 꽂혀 있는 콘센트들 중 다음에 올 가장 빠른 순서를 비교하여 그 중 제일 낮은 친구를 바꿔주면 된다.

    즉, 제일 늦게 등장하는 전기용품을 바꿔주면 된다.

    (제일 낮은 친구는 아예 순서가 없는 친구 일 수도 있다.)

    비워 준뒤에, 새 전기용품으로 갈아 끼워 주자.

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

public class 멀티탭스캐줄링 {
    private static ArrayList<Integer>[] priority;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strArr = br.readLine().split(" ");
        int N = Integer.parseInt(strArr[0]);
        int K = Integer.parseInt(strArr[1]);

        strArr = br.readLine().split(" ");
        int[] intArr = new int[K + 1]; // 주어진 전기용품 순서. 1번째 부터 K번째 까지
        priority = new ArrayList[K+1]; // 각 전기용품의 순서들을 담은 인접리스트?
        for (int i = 0; i <= K; i++) {
            priority[i] = new ArrayList<>();
        }
        for (int i = 1; i <= K; i++) { // i는 순서
            intArr[i] = Integer.parseInt(strArr[i-1]);
            priority[intArr[i]].add(i);
        }
        int temp = 0;
//        for (ArrayList<Integer> arrayList : priority) {
//            System.out.print(temp++ + ": ");
//            for (Integer i : arrayList) {
//                System.out.print(i + " ");
//            }
//            System.out.println();
//        }

        // 콘센트 N개 구멍에 꽂혀 있음
        Set<Integer> nowConcents = new HashSet<>(N);

        // 탐색
        int answer = 0;
        for (int i = 1; i <= K; i++) {
            if(nowConcents.size() != N || nowConcents.contains(intArr[i])){ // 처음 콘센트 자리가 비어 있거나, 같은 전기용품일 때
                nowConcents.add(intArr[i]);
                priority[intArr[i]].remove(0);
//                for (Integer nowConcent : nowConcents) {
//                    System.out.print(nowConcent + " ");
//                }
//                System.out.println();
                continue;
            }
            // 콘센트하나 비워줘야돼
            int getMax = 0;
            int removingConcent = 0;
            for (Integer nowConcent : nowConcents) {
                if(priority[nowConcent].isEmpty()){
                    removingConcent = nowConcent;
                    break;
                }
                if(getMax < priority[nowConcent].get(0)){
                    getMax = priority[nowConcent].get(0);
                    removingConcent = nowConcent;
                }
            }
            nowConcents.remove(removingConcent);
            nowConcents.add(intArr[i]);
            priority[intArr[i]].remove(0);
            answer++;
//            for (Integer nowConcent : nowConcents) {
//                System.out.print(nowConcent + " ");
//            }
//            System.out.println();
        }
        System.out.println(answer);
    }
}

주석을 해제하고 출력을 하면 아래와 같은 결과가 나온다.

:이 있는 부분은 위에서 설명한 각 전기용품의 순서들을 담은 priority를 보여준 것이고

아래는 set(현재 콘센트 상태)가 변화되어 가는 모습을 보여준다.

문제의 예제로 했을 때

 

사용해본 예제로 했을 때

주석 제거 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

public class 멀티탭스캐줄링 {
    private static ArrayList<Integer>[] priority;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strArr = br.readLine().split(" ");
        int N = Integer.parseInt(strArr[0]);
        int K = Integer.parseInt(strArr[1]);

        strArr = br.readLine().split(" ");
        int[] intArr = new int[K + 1]; // 주어진 전기용품 순서. 1번째 부터 K번째 까지
        priority = new ArrayList[K+1]; // 각 전기용품의 순서들을 담은 인접리스트?
        for (int i = 0; i <= K; i++) {
            priority[i] = new ArrayList<>();
        }
        for (int i = 1; i <= K; i++) { // i는 순서
            intArr[i] = Integer.parseInt(strArr[i-1]);
            priority[intArr[i]].add(i);
        }
        int temp = 0;

        // 콘센트 N개 구멍에 꽂혀 있음
        Set<Integer> nowConcents = new HashSet<>(N);

        // 탐색
        int answer = 0;
        for (int i = 1; i <= K; i++) {
            if(nowConcents.size() != N || nowConcents.contains(intArr[i])){ // 처음 콘센트 자리가 비어 있거나, 같은 전기용품일 때
                nowConcents.add(intArr[i]);
                priority[intArr[i]].remove(0);
                continue;
            }
            // 콘센트하나 비워줘야돼
            int getMax = 0;
            int removingConcent = 0;
            for (Integer nowConcent : nowConcents) {
                if(priority[nowConcent].isEmpty()){
                    removingConcent = nowConcent;
                    break;
                }
                if(getMax < priority[nowConcent].get(0)){
                    getMax = priority[nowConcent].get(0);
                    removingConcent = nowConcent;
                }
            }
            nowConcents.remove(removingConcent);
            nowConcents.add(intArr[i]);
            priority[intArr[i]].remove(0);
            answer++;
        }
        System.out.println(answer);
    }
}

 

 

개선전략

 

사용해본 예제

3 12
2 3 1 4 5 6 2 3 1 1 1 1

answer: 4