BOJ) 멀티탭 스케줄링

멀티탭 스케줄링

1700번: 멀티탭 스케줄링

N개의 구멍이 있는 멀티탭이 주어지고, 멀티탭 사용을 해야하는 전자제품의 순서가 K 개 주어진다.

전자제품은 1 ~ K 번의 고유 숫자를 가지고 있다.

코드는 O(k^2*n)의 시간 복잡도를 보이지만, N과 K의 최댓값이 100이기 때문에 크게 적당히 빠른 속도를 보여준다.

 

우선 멀티탭에 꽂혀있는 전자제품을 파악하기 위해 list를 선언해주었다.

k개의 대기 열을 돌면서, 멀티탭에 구멍이 있는지 확인했다.남은 구멍이 없는 경우, 현재 멀티탭에 꽂혀있는 전자제품 중 가장 나중에 멀티탭을 이용해야하는 전자제품을 골라 코드를 뽑아주었다.이를 판별하기 위해, 몇 번째에서 요청이 들어오는지를 파악할 lastIdxArr를 선언했고, 앞으로 이용계획이 없는 전자제품을 골라내주기 위해 Iteger의 최댓값으로 초기화해주었다.

 

남은 요청 대기열을 돌면서 뽑아야하는 전자제품의 인덱스를 저장했다면,  해당 전자제품의 코드를 뽑고 count를 증가시켜 답을 구했다.

 

 

코드

 

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

public class MultiTapScheduling_1700 {
  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()), k = Integer.parseInt(st.nextToken());
    int[] products = new int[k], remains = new int[k+1];
    remains[0] = Integer.MAX_VALUE;

    st = new StringTokenizer(br.readLine());
    for(int i=0; i<k; i++) {
      int type =Integer.parseInt(st.nextToken());
      products[i] = type;
      remains[type]++;
    }

    br.close();
    solution(n, k, products, remains);
  }

  private static void solution(int n, int k, int[] products, int[] remains) {
    List<Integer> multiTap = new ArrayList<>();
    int answer =0;

    for(int i=0; i<k; i++) {
      int product = products[i];
      if(multiTap.contains(product)) {
        continue;
      }
      if(multiTap.size() ==n) {
        int[] lastIdxArr = new int[n];
        Arrays.fill(lastIdxArr, Integer.MAX_VALUE);
        for(int j=0; j<n; j++) {
          int target = multiTap.get(j);
          for(int l=i+1; l<k; l++) {
            if(target == products[l]) {
              lastIdxArr[j] = l;
              break;
            }
          }
        }
        int maxProductIdx =0, maxLastIdx = lastIdxArr[maxProductIdx];
        for(int j=1; j<n; j++) {
          if(maxLastIdx < lastIdxArr[j]) {
            maxLastIdx = lastIdxArr[j];
            maxProductIdx = j;
          }
        }
        multiTap.remove(maxProductIdx);
        answer++;
      }
      multiTap.add(product);
    }
    System.out.println(answer);
  }
}