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

 

 

 

문제 출저

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

1700번: 멀티탭 스케줄링

 

 

 

문제 풀이

구멍이 n개인 멀티탭이 주어집니다. k 번의 전기용품이 주어집니다. 전기용품은 자신의 차례일 때 멀티탭에 꼽혀야 합니다. 멀티탭에 콘센트를 뽑는 횟수의 최소값을 구해야 합니다. 

 

 

그리디 방식으로 문제를 풀었습니다.

멀티탭이 비어있을 경우 전기용품을 꽂습니다.

멀티탭이 가득 차 있을 경우 2가지 로직을 수행합니다.

먼저, 멀티탭에 꽂혀있는 전기용품이 다음에 쓰일지를 확인합니다. 다음에 쓰이지 않을 전기용품부터 멀티탭에 뽑습니다.

만약 멀티탭에 꽂혀있는 전기용품이 모두 다음에 쓰인다면 가장 나중에 쓰일 것을 뽑습니다. 

 

이 로직을 구현하기 위해 Queue<Integer>[] toolOrder 변수를 만들었습니다.

전기용품은 1부터 k까지 주어집니다. 그러므로 new Queue[k]로 선언하고 각각의 전기용품의 순서를 저장합니다.

toolOrder[index].isEmpty()를 통해 다음에 사용하는지 여부를 파악했습니다.

toolOrder[index].peek()를 통해 현재 꽂혀있는 전기용품의 다음 사용 순서를 파악해서 나중에 오는 것을 찾았습니다.

 

 

 

소스코드

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

/*
멀티탭 스케줄링
https://www.acmicpc.net/problem/1700

뽑는 갯수를 최소화하고 싶다.
어떤 것을 뽑아야 하는지 정하는게 관건이다.

멀티탭이 비어있을 경우 그냥 꼽습니다.
멀티탭이 가득 차 있다면 뽑을 것을 선택합니다.

콘센트 중 다음에 필요하지 않는 것을 우선으로 뽑습니다.
만약 모든 콘센트가 다음에 필요하다면 가장 나중에 필요한 것을 뽑습니다.

전자기기 개인의 차례를 Queue<Integer> toolOrder에 담았습니다.
toolOrder의 사이즈를 통해 다음에 필요한지 여부를 파악했습니다.
toolOrder의 peek를 통해 멀티탭 중에서 가장 나중에 필요한 것을 파악했습니다. 


 */


public class Main {

  static int n; // 멀티탭 구멍 개수
  static int k; // 사용 횟수 K

  static int[] orders;
  static Queue<Integer>[] toolOrder;

  static int[] multitab;
  static boolean[] used;

  static int result;
  static int answer;

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    n = Integer.parseInt(st.nextToken());
    k = Integer.parseInt(st.nextToken());

    // 사용 순서, 사용 횟수 저장
    orders = new int[k];

    toolOrder = new Queue[k+1];
    for(int i = 0; i < k+1; i++) {
      toolOrder[i] = new LinkedList<>();
    }

    st = new StringTokenizer(br.readLine());
    for(int i = 0; i < k; i++) {
      int number = Integer.parseInt(st.nextToken());
      orders[i] = number;
      toolOrder[number].add(i);
    }

    // 멀티탭에 처음 꽂혀있는 상태
    multitab = new int[n];
    used = new boolean[k+1];

    int index = 0;
    int tabIndex = 0;
    for(int i = 0; i < k; i++) {
      if(used[orders[i]] == false) {
        used[orders[i]] = true;
        multitab[tabIndex] = orders[i];
        tabIndex += 1;
      }

      toolOrder[orders[i]].poll();

      if(tabIndex == n) {
        index = i+1;
        break;
      }
    }

    answer = k;
    dfs(index);
    System.out.println(answer);

  }


  // 어떤 것을 뺄지 결정
  public static void dfs(int start) {

//    System.out.println(start);
//    System.out.println(Arrays.toString(multitab));
//    for(int i = 0; i < k+1; i++) {
//      System.out.println(toolOrder[i]);
//    }
//    System.out.println();

    if(start == k) {
      answer = Math.min(answer, result);
      return;
    }

    if(used[orders[start]]) {
      toolOrder[orders[start]].poll();
      dfs(start+1);
    }
    else {
      result += 1;

      int index = -1;

      // 나중에 안 사용하면 그걸 먼저 뺀다.
      for(int i = 0; i < n; i++) {
        if(toolOrder[multitab[i]].isEmpty()) {
          index = i;
        }
      }

      // 모두 다 나중에 사용하면 늦게 나오는 걸 뺀다.
      if(index == -1) {
        int check = 0;
        index = 0;

        for(int i = 0; i < n; i++) {
          if (!toolOrder[multitab[0]].isEmpty()) {
            int order = toolOrder[multitab[i]].peek();
            if(check < order) {
              check = order;
              index = i;
            }
          }
        }
      }




      used[multitab[index]] = false;
      used[orders[start]] = true;
      multitab[index] = orders[start];
      toolOrder[orders[start]].poll();
      dfs(start+1);


    }

  }

}