[Javascript] 프로그래머스 - 서버 증설 횟수

문제 설명

온라인 게임 운영 시, 동시 접속자 수가 증가함에 따라 추가 서버가 필요하다. 한 대의 서버는 m명의 이용자를 감당할 수 있으며, 추가된 서버는 k시간 동안 유지된다. 주어진 players 배열을 기반으로, 모든 시간대에서 필요한 최소 서버 증설 횟수를 구하는 문제이다.

---

제한 사항

• players의 길이 = 24 (각 시간대별 이용자 수)
• 0 ≤ players[i] ≤ 1,000
• 1 ≤ m ≤ 1,000
• 1 ≤ k ≤ 24

---

해결 방법

알고리즘: 그리디 (탐욕법)

• curServer: 현재 운영 중인 서버 개수
• stopServer: 특정 시간에 운영이 종료될 서버를 추적하는 배열
• 각 시간대(i)마다 현재 운영 중인 서버 개수를 갱신
• 현재 서버로 감당할 수 없는 경우 추가 서버 개수 계산 및 증설
• 증설된 서버는 k시간 후에 해제되도록 stopServer에 기록
• 모든 시간대에 대해 위 과정을 반복하여 최소 증설 횟수(answer)를 구함

---

시간 복잡도

• players의 길이가 24로 고정되어 있으므로 O(1)
• 각 시간대에 대해 일정한 연산을 수행하므로 매우 효율적

---

구현 코드

function solution(players, m, k) {
  let answer = 0;
  let stopServer = new Array(players.length + k).fill(0);
  let curServer = 1;

  players.forEach((item, index) => {
    curServer -= stopServer[index];

    if (curServer * m <= item) {
      const newServer = Math.floor((item + m - curServer * m) / m);

      curServer += newServer;
      stopServer[index + k] += newServer;
      answer += newServer;
    }
  });

  return answer;
}