백준 JS 8980번 택배 그리디

 

8980번: 택배

푸는데 상당히 오래 걸렸습니다. 5시간 정도 걸렸습니다..

처음 문제를 풀었을 때 15점에서 멈춰서 어디서 잘못된 건지 한참을 찾았는데, 처음 풀이방법이 맞긴 맞아서 코드를 새로 짰습니다.

개인적으로 특히 그리디 문제를 풀 때 코드가 더러워 지는데, 그리디 연습을 많이 해야겠네요..

풀이 방법

풀이 자체는 간단합니다.

1. 데이터를 정렬합니다. 출발 마을을 기준으로 오름차순으로 정렬을 해줍니다.
2. 출발 마을이 같을 경우 도착 마을이 빠른 순서대로 정렬을 해줍니다.
3. 순회를 시작합니다.
4. 순회 중인 데이터의 시작 마을보다 숫자가 작은 마을에 도착해야하는 물건을 트럭에서 빼고, 정답에 더해줍니다.
5. 순회 중인 데이터의 {도착마을, 물건} 객체를 만들어 트럭배열에 push합니다.
6. 트럭 배열을 도착마을 기준 오름차순으로 정렬합니다.
7. 무게가 C보다 무겁다면 도착마을이 가장 늦는 마을의 물건을 트럭의 무게가 C가 될 때까지 뺍니다.
8. 4번~7번을 반복합니다.
9. 순회가 끝나면 트럭에 있는 물건들을 정답에 더해줍니다
10. 정답을 출력합니다.

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n");
const [N,C] = input.shift().split(" ").map(Number)
const M = +input.shift()
const data = input.map(v => v.split(" ").map(Number))

//출발마을 기준으로, 혹은 출발마을이 같다면 도착마을 기준으로 오름차순 정렬
data.sort((a,b)=> a[0]===b[0] ?a[1]-b[1] :a[0]-b[0])

let truck = []; //{도착, 개수}객체를 푸쉬합니다.
let weight = 0;
let answer = 0;
for(let [send,receive,count] of data){
  if(send > receive){
    continue;
  }
	//도착마을이 현재 순회중인 마을보다 작은 물건들을 트럭에서 뺍니다.
  let pass = truck[0]
  while(pass && pass.town <= send){
    truck.shift()
    weight -= pass.number
    answer += pass.number
    pass = truck[0]
  }
	
	//현재 마을에서 보낼 물건을 트럭에 {도착,개수} 객체로 푸쉬합니다.
  truck.push({town:receive, number : count})
	
	//도착마을 기준으로 트럭배열을 정렬합니다.
  truck.sort((a,b)=>a.town-b.town)
  weight += count;
	//무게를 맞출때 까지 pop()하여 무게를 맞춥니다. (정렬을 하였으므로 pop()되는 객체는 도착마을이 가장 늦는 순서대로)
  while(weight > C){
    const temp = truck.pop()
    weight -= temp.number
    if(weight < C){
      temp.number = C-weight
      weight += C-weight
      truck.push(temp)
    }
  }
}

//트럭에 남아있는 물건을 정답에 더해줍니다.
for(let {number} of truck){
  answer += number
}
console.log(answer)

 

이 문제도 1700번 멀티탭 문제와 비슷한 유형입니다.