프로그래머스 코드챌린지: 서버 증설 횟수 최적화 분석

1. 문제 개요

온라인 게임 서버를 운영하는 상황에서, 시간대별로 게임 이용자 수가 주어졌을 때 최소한의 서버 증설 횟수를 계산하는 문제입니다.

• players[i] → i~i+1시 사이의 게임 이용자 수
• m → 서버 1대가 감당할 수 있는 최대 이용자 수
• k → 증설된 서버가 유지되는 시간(운영 기간)
• 서버 1대는 m명까지 감당할 수 있으며, m명 단위로 추가 증설이 필요합니다.
• 한 번 증설한 서버는 k시간 동안 운영된 후 자동 반납됩니다.
• 0~23시까지 이용자 수를 감당하기 위해 서버를 최소 몇 번 증설해야 하는지를 계산해야 합니다.

---

2. 기존 코드 분석

📌 기존 코드 (C++)

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> players, int m, int k) {
    int answer = 0;
    vector<int> server(25, 0);  // 운영 중인 서버 개수를 저장

    for(int i = 0; i < players.size(); i++){
        if(players[i] - (m * server[i+1]) >= m) {  // 현재 서버로 감당 불가능할 때
            int a = (players[i] - (m * server[i+1])) / m;  // 필요한 서버 개수 계산
            for(int j = i+1; j <= i+k; j++) {  // 서버 운영 범위 설정
                if(j <= 24){
                    server[j] += a;
                }
            }
            answer += a;  // 증설 횟수 누적
        }
    }
    return answer;
}

📌 기존 코드의 문제점

1. 연산 순서 오류
   • players[i] - (m * server[i+1]) / m 에서 / m 연산이 m * server[i+1]보다 먼저 수행되어 오차 발생 가능.
   • 올바른 표현: (players[i] - (m * server[i+1])) / m.
2. 서버 유지 관리가 정확하지 않음
   • server[i+1]을 사용해 현재 서버 개수를 참조하는데, 실제 운영 중인 서버를 추적하는 방식이 명확하지 않음.
   • server 배열이 운영 중인 서버 개수를 정확히 반영하지 못함.
3. 증설 횟수 계산 오류
   • answer++ 대신 answer += a;를 사용했으나, 필요 이상으로 서버를 추가하는 경우가 있음.

---

3. 개선된 코드

✔️ 최적화된 코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> players, int m, int k) {
    int answer = 0;
    vector<int> active_servers(24, 0);  // 현재 운영 중인 서버 개수 저장

    for (int i = 0; i < 24; i++) {
        int needed_servers = (players[i] + m - 1) / m;  // 필요한 총 서버 개수 (올림)
        int active_now = active_servers[i];  // 현재 운영 중인 서버 개수
        int additional_servers = max(0, needed_servers - active_now);  // 부족한 서버 개수

        // 추가적으로 필요한 서버 증설
        if (additional_servers > 0) {
            answer += additional_servers;  // 증설 횟수 추가
            for (int j = i; j < min(i + k, 24); j++) {
                active_servers[j] += additional_servers; // 운영 시간 동안 서버 유지
            }
        }
    }
    return answer;
}

📌 개선 사항

1. 필요한 서버 개수를 정확히 계산
   • (players[i] + m - 1) / m 사용 → 올림(ceil) 효과 적용.
   • needed_servers - active_now 를 계산하여 실제 부족한 서버 개수만 추가.
2. 운영 중인 서버를 정확하게 유지
   • active_servers 배열을 활용하여 k시간 동안 운영되는 서버를 정확히 반영.
3. 증설 횟수 정확한 누적
   • answer += additional_servers; 로 정확한 횟수 저장.

---

4. 더 나은 알고리즘 접근법

기본적으로 탐욕적 알고리즘 (Greedy Algorithm) 을 사용하여 각 시간대마다 필요한 최소한의 서버를 추가하는 방식으로 해결합니다.

하지만, 효율성을 높이려면 다음과 같은 알고리즘을 사용할 수도 있습니다.

🔹 더 나은 방법 1: 누적 합 (Prefix Sum) 활용

• 서버의 증설 및 유지 정보를 한 번에 기록하고, 누적 합 배열을 사용하여 빠르게 계산할 수 있습니다.
• players[i] 값이 큰 경우에도 반복문을 줄여 연산 속도를 개선 가능.

🔹 더 나은 방법 2: 슬라이딩 윈도우 (Sliding Window) 활용

• k시간 동안 서버가 유지되므로, 현재 필요한 서버 수를 슬라이딩 윈도우 방식으로 갱신할 수 있습니다.
• 중복 계산을 줄이고, 불필요한 연산을 제거할 수 있어 더 효율적인 풀이가 가능.

---

5. 결론

✅ 기존 코드의 문제점을 해결하고, 필요한 서버를 정확하게 증설하도록 개선
✅ 탐욕적 알고리즘(Greedy)을 사용하여 최적화된 해법을 적용
✅ 더 나은 해결 방법으로 누적 합(Prefix Sum)과 슬라이딩 윈도우(Sliding Window) 고려 가능

이제 더 빠르고 정확한 서버 증설 관리가 가능해졌습니다! 🚀

---

6. 코드 테스트

int main() {
    vector<int> players1 = {0, 2, 3, 3, 1, 2, 0, 0, 0, 0, 4, 2, 0, 6, 0, 4, 2, 13, 3, 5, 10, 0, 1, 5};
    int m1 = 3, k1 = 5;
    cout << solution(players1, m1, k1) << endl; // 예상 결과: 7

    vector<int> players2 = {0, 0, 0, 10, 0, 12, 0, 15, 0, 1, 0, 1, 0, 0, 0, 5, 0, 0, 11, 0, 8, 0, 0, 0};
    int m2 = 5, k2 = 1;
    cout << solution(players2, m2, k2) << endl; // 예상 결과: 11

    vector<int> players3 = {0, 0, 0, 0, 0, 2, 0, 0, 0, 1, 0, 5, 0, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1};
    int m3 = 1, k3 = 1;
    cout << solution(players3, m3, k3) << endl; // 예상 결과: 12

    return 0;
}

---

💡 이 글을 통해 "서버 증설 횟수 문제"를 이해하고, 더 효율적인 알고리즘을 고민하는 데 도움이 되길 바랍니다! 🚀