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

문제링크: https://www.acmicpc.net/problem/1700

1700번: 멀티탭 스케줄링

 

이 문제에 처음 접근할때 완탐을 생각했으나, 시간 복잡도가 3¹⁰⁰ 이 나와 안된다 라고 판단했다.

그래서 그리디 하게 접근을 했다. 스택을 하나 만들어 [사용횟수, 기기명] 으로 push 하여 사용횟수를 기준으로 내림차순 정렬을 했다. 그리고 멀티탭이 꽉찬경우 스택의 최상단을 pop 하고 새로운 기기를 넣는 방식을 사용했다. 

하지만 위 방법으로도 문제를 풀 수 없었고, 도무지 해결방법이 떠오르지 않아 풀이를 보았다.

 

그리디 라는 문제 유형은 맞췄다.

1. 우선 크게 멀티탭의 공간이 남았을 경우와 그렇지 않은 경우 2가지로 분리할 수 있다.

2. 멀티탭의 공간의 남았을 경우 

    2-1. 멀티탭 배열에 해당기기 넘버를 넣는다.

3. 멀티탭 공간이 남아있지 않을 경우

    3-1. 해당기기 넘버가 멀티탭 배열에 포함 되어있는지 확인한다. 만약 배열에 포함되어있다면 넣을 필요가 없으므로 continue 한다.

    3-2. 멀티탭 배열에 담겨있는 기기 넘버중 가장 늦게 나오는 넘버를 찾아 새로운 기기의 넘버로 교체한다. 

 

const fs = require('fs');

BOJkey = true;

const input = fs
  .readFileSync(BOJkey ? './javascript/1700/input.txt' : './dev/stdin')
  .toString()
  .trim()
  .split('\n')
  .map(el => el.split(' ').map(Number));

const [N, K] = input.shift();
const data = input.pop();
let count = 0;
const multitap = Array.from({ length: N }, () => 0);

data.forEach((electricalAppliance, electricalApplianceIndex) => {
  let [hasEmptySpace, emptySpaceIndex] = [false, 0];

  multitap.forEach((appliance, index) => {
    if (appliance === 0 && multitap.indexOf(electricalAppliance) === -1) {
      hasEmptySpace = true;
      emptySpaceIndex = index;
    }
  });

  if (hasEmptySpace) {
    multitap[emptySpaceIndex] = electricalAppliance;
  }

  if (!hasEmptySpace) {
    if (multitap.indexOf(electricalAppliance) !== -1) return;

    let [order, changeMultitapIndex] = [Number.MIN_SAFE_INTEGER, -1];

    multitap.forEach((appliance, index) => {
      let temp = Number.MAX_SAFE_INTEGER;
      for (let i = electricalApplianceIndex + 1; i < data.length; i++) {
        if (appliance === data[i]) {
          temp = i;
          break;
        }
      }

      if (temp > order) {
        order = temp;
        changeMultitapIndex = index;
      }
    });

    multitap[changeMultitapIndex] = electricalAppliance;
    count++;
  }
});

console.log(count);

 

시간복잡도: O(N² * K)
indexOf - O(n)