문제 개요

문제: 과제

분류: 자료 구조, 그리디 알고리즘, 정렬, 우선순위 큐

난이도: 골드3

문제 풀이

과제 마감일 중 가장 긴 마감일을 maxDay, 과제 정보를 담는 배열 homeworks가 있다고 하자.

1. homeworks를 과제 점수를 기준으로 내림차순 정렬한다.
2. maxDay가 0이 될 때까지 아래를 반복한다.
   1. homeworks를 차례대로 탐색하면서 현재 과제의 남은 일수가 maxDay보다 같거나 크다면 정답 변수에 현재 과제의 점수를 더한다.
      해당 과제가 끝났다는 의미로 과제의 남은 일수를 0으로 변경하고 반복문을 종료한다.
   2. maxDay를 1만큼 감소시킨다.
3. 정답을 출력한다.

즉, 과제 마감일을 하루씩 줄여가며 기간에 해당하는 과제 중 점수가 가장 높은 과제를 하나씩 끝내는 것이다.

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

const solution = (input) => {
  const N = +input.shift();
  let maxDay = 0;
  const homeworks = input.map((v) => {
    const [d, w] = v.split(" ").map(Number);
    maxDay = Math.max(d, maxDay);
    return [d, w];
  });

  homeworks.sort((a, b) => b[1] - a[1]);

  let answer = 0;
  while (maxDay > 0) {
    for (let i = 0; i < N; i++) {
      if (homeworks[i][0] >= maxDay) {
        answer += homeworks[i][1];
        homeworks[i][0] = 0;
        break;
      }
    }
    maxDay--;
  }

  console.log(answer);
};

solution(input);