백준 JS 1700번 멀티탭 스케줄링 그리디

1700번: 멀티탭 스케줄링

문제 푸는 방법을 잘 모르겠어서 시간이 오래 걸렸던 문제.

문제푸는 방법만 알면 간단하게 풀 수 있었다.

풀이 방법

1. 우선 멀티탭에 전기용품을 꼽는다.
2. 순서대로 전기용품을 shift()한다.
3. 멀티탭에 꽂혀있는 물건이 아니라면, 물건을 하나 골라서 플러그를 빼야한다.
4. 플러그 빼는 물건은 가장 늦게 쓰이거나, 나중에 쓰이지 않는 물건의 플러그를 빼야한다.

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n");
const [N,K] = input.shift().split(" ").map(Number)
const data = input[0].split(" ").map(Number)
const mulPlug = []
//중복이 있을 수 있어 아래와 같이 순회로 멀티탭 배열에 물건을 넣습니다.
while(mulPlug.length < N){
  const num = data.shift()
  if(!mulPlug.includes(num)){
    mulPlug.push(num)
  }
}

let answer = 0;
while(data.length !== 0){
  const item = data.shift()
	//멀티탭에 꽂혀있는 물건이면 continue.
  if(mulPlug.includes(item)){
    continue;
  }
	//멀티탭에 꽂혀있는 물건이 이후 언제 다시 쓰이는지를 값으로 가지는 배열 order를 만듭니다. 나중에 쓰이지 않는다면, 값으로 Infinity를 가집니다.
  const order = mulPlug.map((_,i) => [i,Infinity])
  for(let i=0; i<N; i++){
    const temp = mulPlug[i]
    for(let j=0; j<data.length; j++){
      if(data[j] === temp && order[i][1] > j){
        order[i][1] = j
      }
    }
  }
	//가장 늦게 사용되거나, 다시 사용되지 않는 물건을 골라서 플러그에서 뽑고, 새로운 item을 배열에 넣어줍니다.
  const changeIndex = order.sort((a,b)=>b[1]-a[1])[0][0]
  mulPlug[changeIndex] = item;
  answer++
}
console.log(answer)

백준 골드문제 이상의 그리디에서는 위와같은 유형의 문제가 많이 나왔다.

하나의 기준으로 정렬을 해서 뽑고, 뽑은 데이터 중에서 다른 기준으로 정렬을 한 이후 빼버리는 유형.