BOJ 1700 멀티탭 스케줄링

문제

 

1700번: 멀티탭 스케줄링

 

예시 코드

function solution() {
  const [N, K] = input().split(" ").map(Number);
  const order = input().split(" ").map(Number);

  const plugs = new Map();
  let cnt = 0;

  for (let i = 0; i < K; i++) {
    if (plugs.has(order[i])) continue;
    if (plugs.size < N) {
      plugs.set(order[i], true);
      continue;
    }

    // 멀티탭에 꽂혀 있는 기기 중 앞으로 전혀 사용되지 않거나 가장 마지막에 사용되는 기기 찾기
    let max = -1;
    let idx = -1;
    const sliced = order.slice(i + 1);

    for (let [k, v] of plugs) {
      const tmp = sliced.indexOf(k);

      if (tmp === -1) {
        idx = k;
        break;
      }
      if (tmp > max) {
        max = tmp;
        idx = k;
      }
    }

    plugs.delete(idx);
    plugs.set(order[i], true);
    cnt++;
  }

  return cnt;
}

 

풀이

각 기기를 실행 순서에 따라 멀티탭에 꽂아야 합니다. 다만, 구멍의 개수가 제한되어 있기 때문에 모든 기기를 동시에 꽂을 수는 없을 수 있습니다.

 

멀티탭이 꽉 차 있을 때 다른 기기를 꽂으려면 이미 꽂혀 있는 기기의 플러그 중에서 하나를 뽑아야 합니다. 이때, '어떤 순서로 플러그를 뽑아야 플러그를 가장 적게 뽑을 수 있는지'가 문제의 핵심입니다.

 

이를 위해 멀티탭에 꽂혀 있는 기기 중 앞으로 전혀 사용되지 않거나 가장 마지막에 사용되는 기기를 찾습니다.

앞으로 전혀 사용되지 않는 기기가 여러 개라면 그 중 하나를 선택하면 됩니다.

 

e.g.

N = 2, K = 8

기기의 사용 순서가 2 3 2 3 1 2 3 7 인 경우

 

여기서 플러그를 빼야 하는 경우는 5번, 7번, 8번 순서입니다.

 

5번 순서 전까지 꽂혀 있는 플러그는 2번, 3번입니다.

5번 순서 - 가장 마지막에 사용되는 3번 플러그를 빼고 1번 플러그를 꽂습니다. 이제 꽂혀있는 플러그는 1번, 2번입니다.

7번 순서 - 더 이상 사용되지 않는 2번 플러그를 빼고 3번 플러그를 꽂습니다. 이제 꽂혀있는 플러그는 1번, 3번입니다.

8번 순서 - 더 이상 사용되지 않는 1번 플러그를 빼고 7번 플러그를 꽂습니다. 이제 꽂혀있는 플러그는 3번, 7번입니다.

 

따라서 플러그를 빼는 최소 횟수는 3이 됩니다.