[Algorithm] 서버 증설 횟수

목차

---

1. 문제 설명

2. 접근 방식

3. 코드

4. 시간 복잡도 및 공간 복잡도 계산

 

 

 

 

 

1. 문제 설명

---

https://school.programmers.co.kr/learn/courses/30/lessons/389479

프로그래머스

 

 

문제 핵심 조건은 아래와 같다.

• 같은 시간대에 게임을 이용하는 사람이 m명 늘어날 때마다 서버 1대 추가
• n * m <= 어느 시간대의 이용자 < (n + 1) * m → 최소 n대의 증설된 서버가 필요
• k = 5 ) 10시에 증설한 서버는 10 ~ 15시에만 운영

 

0 ~ 23시까지의 모든 게임 이용자를 감당하기 위한 최소 서버 증설 횟수를 구하면 된다. 

 

 

 

2. 접근 방식

---

players의 길이, m, k가 각각 충분히 작고

"매 시각마다 최소한의 서버만 증설"하기 때문에 그리디를 떠올렸다. 

 

 

( 게임 이용자 수 / m )으로 나누면 시각별로 증설해야 할 서버의 수를 구할 수 있다. 

이때 현재 시각에 이미 증설되어 있던 서버가 있다면 그 값을 제해야 실제 증설 횟수를 구할 수 있다. 

즉, 현재 시각에 증설된 서버 개수 = ( 게임 이용자 수 / m ) - ( 이미 증설되어 있던 서버 개수 )

 

 

그렇다면 이미 증설되어 있던 서버 개수는 어디에 기록하면 되는가?

int[] time = new int[24]; // i시각에 증설된 서버의 개수
Arrays.fill(time, 0);

 

어차피 시각은 0 ~ 24시까지만 보면 된다. 

따라서 크기가 24인 int형 배열에 i시에 이미 증설되어 있는 서버의 개수를 저장한다. 

ex) time[0] = 0시에 운영되고 있는 증설 서버 개수

 

현재 시각에 증설된 서버 개수를 구했다면, 해당 서버의 운영 시간을 기록해야 한다. 

서버 한 대가 운영 가능한 시간은 k와 같으므로 현재 시각이 i시라면 i + k시 까지 운영된다. 

 

이를 코드로 구현하면 다음과 같다. 

 

 

 

 

3. 코드

---

import java.util.*;

class Solution {
    public int solution(int[] players, int m, int k) {
        int count = 0; // 서버 증설 횟수 기록
        int[] time = new int[24]; // i시각에 증설된 서버의 개수
        Arrays.fill(time, 0);
        
        for(int i = 0; i < players.length; i++) {
            int player = players[i]; // i ~ i + 1 시각의 게임 이용자 수 
            int nServerCount = player / m; // 증설된 서버의 수
            int now = time[i]; // 현재 시각에 이미 증설되어 있는 서버 개수
            
            if(nServerCount < now || nServerCount < 1) continue;
            count += (nServerCount - now); // 증설 횟수
            
            // 증설된 서버 운영 시간 기록
            for(int j = i; j < i + k; j++) {
                if(j < 24) time[j] += (nServerCount - now);
            }
        }
        
        return count;
        
    }
}

 

 

다 풀고 고민해보니까 만약 players의 길이가 충분히 길었다면 이 방식은 유효하지 않을 것이다. 

players의 길이가 수십만 이상인 경우엔, 우선순위큐로 풀이하는 것이 좋을 것 같다. 

 

아래는 우선순위큐로 풀이한 코드이다. 

 

import java.util.*;

class Solution {
    public int solution(int[] players, int m, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 서버 만료 시각 저장
        int count = 0; // 서버 증설 횟수 기록
        
        for (int i = 0; i < 24; i++) {
            // 1. 만료된 서버 제거
            while (!pq.isEmpty() && pq.peek() <= i) {
                pq.poll();
            }
            
            // 2. 현재 필요한 서버 수
            int player = players[i];
            int nServerCount = player / m;
            int now = pq.size(); // 현재 살아 있는 서버 개수
            
            // 3. 부족하면 증설
            if (now < nServerCount) {
                int add = nServerCount - now;
                count += add;
                
                for (int j = 0; j < add; j++) {
                    pq.offer(i + k); // k시간 뒤 만료
                }
            }
        }
        
        return count;
    }
}

 

 

 

 

4. 시간 복잡도 및 공간 복잡도 계산

---

for (int i = 0; i < players.length; i++) {       // 24번 반복
    int nServerCount = player / m;
    int now = time[i];
    if (nServerCount < now || nServerCount < 1) continue;

    // 증설된 서버 운영 시간 기록
    for (int j = i; j < i + k; j++) {            // 최대 k번 반복
        if (j < 24) time[j] += (nServerCount - now);
    }
}

 

먼저 그리디 코드에서 바깥쪽 반복문은 반복 횟수가 24번으로 고정이고 안쪽 루프는 최대 k번 반복하므로

시간 복잡도는 O(24 * k) = O(1)가 된다. (k는 24 이하)

 

공간 복잡도는 time 배열로 인해 O(1)의 복잡도를 갖는다. 

 

---

for (int i = 0; i < 24; i++) {
    // 1. 만료된 서버 제거
    while (!pq.isEmpty() && pq.peek() <= i) {
        pq.poll();
    }
 }

 

우선순위큐를 사용한 방식 역시 바깥쪽 반복문은 반복 횟수가 24번으로 고정이고

안쪽 반복문의 힙 연산은 log(heap 크기)와 같으므로

전체 증설 횟수가 X번이라고 가정할 때 시간 복잡도는 O(X logX)가 된다.

 

공간 복잡도는 우선순위큐에 증설된 서버 개수를 저장하므로 O(X)와 같다.