[Javascript] 프로그래머스 - 과제 진행하기

문제 설명

루는 여러 개의 과제를 수행해야 하며, 다음과 같은 규칙을 따릅니다.

1. 과제는 정해진 시작 시각이 되면 시작합니다.
2. 새로운 과제를 시작해야 하는 시각이 되면, 진행 중이던 과제는 멈추고 새 과제를 시작합니다.
3. 멈춘 과제는 이후 시간이 생기면 다시 진행합니다.
4. 멈춰둔 과제가 여러 개라면, 가장 최근에 멈춘 과제부터 진행합니다.
5. 과제를 완료한 순서대로 결과를 반환해야 합니다.

---

제한 사항

• 과제 개수는 3개 이상 1,000개 이하입니다.
• 과제 이름은 알파벳 소문자로 이루어져 있으며, 길이는 2~10자입니다.
• 모든 과제의 시작 시각은 겹치지 않으며, "hh:mm" 형식으로 주어집니다.
• 각 과제의 소요 시간은 1분 이상 100분 이하입니다.
• 주어진 과제 목록은 반드시 시간순으로 정렬되어 있지는 않습니다.

---

해결 방법

알고리즘: 스택(Stack) 활용

1. 시간을 비교하기 쉽게 시각을 분 단위로 변환한 후, 시작 시각 기준으로 정렬합니다.
2. 과제 목록을 순회하며
   • 이전 과제의 남은 시간이 있다면, 새 과제 시작 전까지 진행합니다.
   • 새로운 과제가 시작되면 진행 중이던 과제를 스택에 저장하고 새 과제를 시작합니다.
3. 모든 과제를 순회한 후, 스택에 남아 있는 과제를 처리하여 완료 순서를 반환합니다.

---

시간 복잡도

• O(N log N) (정렬) + O(N) (스택 활용) → O(N log N)

---

구현 코드

function getTime(time) {
  return parseInt(time.slice(0, 2)) * 60 + parseInt(time.slice(3));
}

function solution(plans) {
  let answer = [];

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

  let testStack = [];
  let prevTime = 0;

  for (const [test, time, duringStr] of plans) {
    const curTime = getTime(time);
    const during = Number(duringStr);
    let remainingTime = curTime - prevTime;

    while (remainingTime > 0 && testStack.length > 0) {
      const [prevTest, prevDuring] = testStack.pop();

      if (prevDuring > remainingTime) {
        testStack.push([prevTest, prevDuring - remainingTime]);
        break;
      }

      answer.push(prevTest);
      remainingTime -= prevDuring;
    }

    testStack.push([test, during]);
    prevTime = curTime;
  }

  while (testStack.length > 0) {
    answer.push(testStack.pop()[0]);
  }

  return answer;
}