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

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q1000/Q1700.java

멀티탭의 꼿을 수 있는 개수와 사용되어야할 기기가 순서대로 주어진다. 멀티탭에서 제품을 뽑는것을
최소화 할 때, 몇 번 뽑아야하는지 출력하여라.

처음 생각

콘센트의 꼽을 수 있는 수도 100개 꼽는 기기의 수도 최대 100개이다. 수가 작으므로 다 살펴보면서 진행을 하였다.

▶ 현재 꼿혀있는데 똑같은게 들어올 경우는 바로 다음 기기를 봐도 상관없으므로 HashSet을 이용해서 꼿힌 기기들을 관리해 주었다.

다음 생각

꼿혀있지 않을경우 2가지로 나눠진다. 1) 콘센트에 자리가 없을경우 2) 콘센트에 자리가 있을경우 로 나눠진다.

▶ 1)의 경우는 HashSet에 있는 기기들을 가지고 현재 idx 이후로 해당 기기가 있는지 없는지를 판단한다. 만약 해당 기기가 사용안되면 바로 그 기기를 제거해준 후 새로운 기기를 꼽는다.

▶ 해당기기가 또 사용된다면 index를 비교해서 가장 큰 index를 가지고 있는 기기를 제거해준다.

▶ 2)의 경우는 바로 HashSet에 넣어주었다.

다다음 생각

뽑는 경우의 수를 출력하는 것이므로 HashSet에서 remove를 해줄 때 결과값을 +1 시켜주었다.

방안

1) 처음에는 PrioirtyQueue등을 이용해서 효율적으로 구현을 해보려고했었는데 개수가 최대 100개 밖에 안되므로 모든 경우를 살펴보았다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

package baekjoon.q1000;   import java.util.HashSet; import java.util.Scanner;   public class Q1700 {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int n = sc.nextInt(); // 구멍의 개수         int m = sc.nextInt(); // 제품 수         int[] arr = new int[m];         for(int i=0;i<m;i++)             arr[i] = sc.nextInt();           int result = 0;         HashSet<Integer> set = new HashSet<>();         for(int i=0;i<m;i++){             int t = arr[i];             // 이미 꼽혀있는 거면 그대로 가져간다             if(set.contains(t)) continue;             // 새로 꼽아야할 경우             // 1) 다 꼽혀있다면             if(set.size()==n){                 int idx = -3, target = 0;                 for(int tt:set){                     int tIdx = 9999;                     // 제일 안쓰이는 걸 찾자.                     for(int j=i+1;j<m;j++){                         // 똑같은게 있다면 해당 index 저장                         if(tt==arr[j]){                             tIdx = j;                             break;                         }                     }                     // tIdx가 변하지 않았다면 이 뒤로 사용되지 않는다는 것이다.                     if(tIdx==9999){                         target = tt;                         break;                     }else{                         // 가장 나중에 사용되는걸 찾자.                         if(tIdx>idx){                             idx = tIdx;                             target = arr[tIdx];                         }                     }                 }                 // 콘센트 빼주기                 set.remove(target);                 result++;             }             // 2) 남는 곳이 있다면             set.add(t);         }         System.out.println(result);     } }