[Programmers / Level 2] 389479. 서버 증설 횟수 (Java)

💡 Info

• 난이도: Lv2
  프로그래머스 링크: https://school.programmers.co.kr/learn/courses/30/lessons/389479
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/2/서버 증설 횟수

입출력 조건

입출력 예시

문제 이해

• 게임을 이용하는 사람이 m명 늘어나면 -> k시간 동안 지속되는 서버 증설

알고리즘

풀이 시간 : 35분

• 활성 서버 추적

  • 현재 가동 중인 서버 수를 실시간 관리 : runningServers 사용
  • 서버 반납 시점 기록 및 스케줄링 : shutDownSchedule 배열 사용

• 서버 반납 처리

  • 시간 t 시작 -> shutDownSchedule[t]에 기록된 서버 수를 runningServers에서 빼는 방식으로 진행
  • players[t] / m -> 현재 시점에 필요한 최소 서버 수 계산(정수)
  • runningServers < requiredServers인 경우 차액만큼 서버 증설
    • 차액 : add = requiredServers - runningServers
  • 증설된 서버 -> k 시간 후 반납 예정 -> 서버 수명이 종료되면 자동 반납

import java.util.*;

class Solution {
    public int solution(int[] players, int m, int k) {
        int n = players.length;
        int[] shutDownSchedule = new int[n + k]; // t+k 시점에 반납될 서버 수
        int runningServers = 0;   // 지금 돌고 있는 서버 수
        int totalAdded = 0;   // 총 증설된 서버 수(최종 값)

        for (int t = 0; t < n; t++) {
            // k 시간이 지난 후 반납될 서버 제거
            runningServers -= shutDownSchedule[t];

            // 추가 서버 수
            int requiredServers = players[t] / m;

            
            //부족한 만큼 증설
            if (runningServers < requiredServers) {
                int add = requiredServers - runningServers;
                totalAdded     += add;
                runningServers += add;

                // k 시간 후 서버 반납
                if (t + k < shutDownSchedule.length) {
                    shutDownSchedule[t + k] += add;
                }
            }
        }
        return totalAdded;
    }
}

결과

✍️ 오답 노트

import java.util.*;

class Solution {
    public int solution(int[] requests, int maxUsersPerServer, int activeTime) {
        int totalServersAdded = 0;
        int[] servers = new int[requests.length + activeTime];
        long activeCapacity = 0;

        for (int time = 0; time < requests.length; time++) {
            if (time - activeTime >= 0) {
                activeCapacity -= (long) servers[time - activeTime] * maxUsersPerServer;
            }

            int currentRequest = requests[time];
            if (activeCapacity >= currentRequest) continue;

            long required = currentRequest - activeCapacity;
            int serversToAdd = (int) ((required + maxUsersPerServer - 1) / maxUsersPerServer);

            servers[time] = serversToAdd;
            totalServersAdded += serversToAdd;
            activeCapacity += (long) serversToAdd * maxUsersPerServer;
        }
        return totalServersAdded;
    }
}

처리 가능한 유효 용량을 잘못 계산

• 서버 증설 그 순간부터 activeTime이 발생되는 유효 범위가 의도와 다르게 계산되고 있음
• activeTime이 지난 시점의 서버는 만료되니, 그 수만큼 처리 용량에서 빼자는 의도였지만 이 부분이 다소 모호하여 연산 오류가 나는 것으로 파악

if (time - activeTime >= 0) {
    activeCapacity -= (long) servers[time - activeTime] * maxUsersPerServer;
}

틀린 이유 상세 분석

• 요청량은 시점별로 발생해야하나,activeCapacity는 누적치처럼 유지됨

  • players[i]는 순간 요청량인데, activeCapacity는 "가상의 누적 처리 용량"처럼 처리되는 것

• activeCapacity

  • 처리할 때, 단순히 빼고 더하는 방식으로 처리하려다보니 유효 서버 수 × 처리량이 일치하지 않는 것
  • 이전 처리량을 저장하지 않아서 이전 시점에 필요 이상으로 서버를 증설했을 때의 경우가 명확하게 반영되지 않음(그 여유 공간이 다음 시점에 사용할 수 있는 것이 되어버림)

해결 방안

• 처리 가능한 유효 용량을 최근 k시간 동안의 서버로 추적
• 각 시간마다 servers[t] 서버가 증설
• 해당 서버는 t, t+1, ..., t + k - 1 시간의 요청을 커버