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

문제 개요

온라인 게임 운영에서 시간대별 이용자 수에 따라 서버를 최소한으로 증설하는 문제입니다.

문제 조건

• 이용자 수: 각 시간대(0~23시)별 게임 이용자 수
• m: 서버 한 대로 감당할 수 있는 최대 이용자 수
• k: 서버 한 대가 운영 가능한 시간
• 목표: 모든 게임 이용자를 감당하기 위한 최소 서버 증설 횟수

핵심 규칙

1. 서버 필요 조건: 이용자 수가 m명 이상일 때만 서버가 필요
2. 필요한 서버 수: Math.floor(이용자 수 / m)
3. 서버 운영 기간: 증설한 서버는 k시간 동안 운영
4. 증설 횟수: 같은 시간대에 서버를 x대 증설했다면 해당 시간대의 증설 횟수는 x회

예시 분석

예시 1: m=3, k=5

시각    이용자    필요서버    운영서버    증설횟수
0~1     0        0          0          0
1~2     2        0          0          0
2~3     3        1          1          1
3~4     3        1          1          0
4~5     1        0          1          0
5~6     2        0          1          0
6~7     0        0          1          0
7~8     0        0          0          0
...
10~11   4        1          1          1
11~12   2        0          1          0
12~13   0        0          1          0
13~14   6        2          2          1
14~15   0        0          2          0
15~16   4        1          1          0
16~17   2        0          1          0
17~18   13       4          4          3
18~19   3        1          3          0
19~20   5        1          3          0
20~21   10       3          3          0
21~22   0        0          3          0
22~23   1        0          0          0
23~24   5        1          1          1

총 증설 횟수: 7회

핵심 발견

1. 시각 1~2: 이용자 2명 < m=3 → 서버 0대 (서버 증설 불필요)
2. 시각 2~3: 이용자 3명 = m=3 → 서버 1대 필요, 증설 1회
3. 시각 4~5: 이용자 1명 < m=3 → 서버 0대 필요, 하지만 이전에 증설한 서버가 계속 운영
4. 서버 운영 특성: 서버는 k시간 동안 운영되므로 이용자 수와 관계없이 계속 운영

알고리즘 설계

접근법: 그리디 알고리즘

각 시간대를 순회하면서 부족한 서버만큼 증설하는 방식입니다.

핵심 로직

1. 필요한 서버 수 계산: Math.floor(이용자 수 / m)
2. 부족한 서버 확인: 현재 시간대에 필요한 서버 수 - 운영 중인 서버 수
3. 서버 증설: 부족한 만큼 증설하고 k시간 동안 운영되도록 표시
4. 증설 횟수 누적: 총 증설 횟수에 추가

시간복잡도 분석

• 시간복잡도: O(N * k) ≈ O(N) (k는 최대 24로 상수)
• 공간복잡도: O(N)

구현 코드

function solution(players, m, k) {
  const HOURS = 24;

  // 각 시간대별 필요한 서버 수 계산
  const required = new Array(HOURS);
  for (let i = 0; i < HOURS; i++) {
    required[i] = Math.floor(players[i] / m);
  }

  // 각 시간대별 운영 중인 서버 수 추적
  const activeServers = new Array(HOURS).fill(0);

  // 총 증설 횟수
  let totalInstallations = 0;

  // 각 시간대를 순회하면서 부족한 서버 증설
  for (let i = 0; i < HOURS; i++) {
    // 현재 시간대에 부족한 서버 수
    const shortage = required[i] - activeServers[i];

    if (shortage > 0) {
      // 부족한 만큼 증설
      totalInstallations += shortage;

      // 증설한 서버가 운영될 시간대 표시
      for (let j = i; j < Math.min(i + k, HOURS); j++) {
        activeServers[j] += shortage;
      }
    }
  }

  return totalInstallations;
}

문제 해결 과정

1단계: 문제 이해

처음에는 단순히 Math.ceil(이용자 수 / m)으로 필요한 서버 수를 계산했습니다.

2단계: 예시 분석

예시 표를 분석하면서 다음을 발견했습니다:

• 이용자 수가 m명 미만이어도 서버가 운영될 수 있음
• 서버는 k시간 동안 운영되므로 이전에 증설한 서버가 계속 운영됨

3단계: 규칙 재정의

문제를 다시 읽어보니 핵심 규칙을 발견했습니다:

• 필요한 서버 수 = Math.floor(이용자 수 / m)
• 이용자 수가 m의 배수일 때만 서버가 필요

4단계: 알고리즘 구현

그리디 알고리즘으로 각 시간대를 순회하면서 부족한 서버만큼 증설하는 방식으로 구현했습니다.

핵심 포인트

1. 문제 해석의 중요성

문제를 정확히 이해하는 것이 가장 중요합니다. 처음에는 Math.ceil을 사용했지만, 실제로는 Math.floor가 맞았습니다.

2. 예시 분석의 활용

제공된 예시를 자세히 분석하면서 문제의 핵심 규칙을 파악할 수 있었습니다.

3. 그리디 알고리즘의 적합성

이 문제는 그리디 알고리즘이 최적해를 보장합니다. 어차피 필요한 시점에 증설해야 하므로, 일찍 증설할수록 더 많은 시간대를 커버할 수 있습니다.

4. 시간복잡도 최적화

• 불필요한 중첩 반복문 제거
• 효율적인 자료구조 사용
• O(N) 수준의 시간복잡도 달성