[programmers] 기능 개발 (in JS)

문제

기능 개발

Fact

• 배포까지 필요한 날짜는 다음과 같이 계산한다.

Math.ceil((100 - progress) / speed)

• 현재 기능의 배포 가능한 날짜가 앞선 기능의 배포 가능 날짜보다 작거나 같을 경우, 이전 작업과 함께 배포될 수 있다.

• 한 번의 순회로 확인하려면, stack을 이용하여 stack top에 있는 기능의 배포 가능 날짜와 비교해야 한다.

접근

• 배포 가능한 날짜를 담은 days stack과 각 날짜에 배포할 기능의 수를 담은 count stack을 선언한다.

• 기능을 순회하며 다음을 반복한다.

  • 배포 가능한 날짜를 구한다.

  Math.ceil((100 - progress) / speed)

  • days가 빈 스택이거나, days의 top 보다 현재 기능의 배포 날짜가 더 클 경우, days에 day를 푸쉬하고, count에 1을 push한다.
  • 위의 경우가 아닐 경우, 이전 날짜의 기능과 함께 배포할 수 있으므로, count의 top에 1을 더한다.

• count stack을 반환한다.

복잡도

• 공간 복잡도 : O(N)
• 시간 복잡도 : O(N)

코드

class Stack {
  constructor() {
    this.s = [];
  }
  empty() {
    return this.s.length === 0;
  }
  top() {
    return this.s[this.s.length - 1];
  }
  push(item) {
    this.s.push(item);
  }
  pop() {
    const [top] = this.s.splice(this.s.length - 1, 1);
    return top;
  }
  values() {
    return [...this.s];
  }
}
function solution(progresses, speeds) {
  const count = new Stack();
  const days = new Stack();

  progresses.forEach((progress, i) => {
    const day = Math.ceil((100 - progress) / speeds[i]);
    if (days.empty() || days.top() < day) {
      days.push(day);
      count.push(1);
    } else {
      const top = count.pop();
      count.push(top + 1);
    }
  });
  return count.values();
}