[Java] 프로그래머스 문제 - 서버 증설 횟수

오늘도 마찬가지로 풀어본 문제는 프로그래머스의 서버 증설 횟수 라는 문제를 풀어보았다.

---

문제 설명

당신은 온라인 게임을 운영하고 있습니다. 같은 시간대에 게임을 이용하는 사람이 m명 늘어날 때마다 서버 1대가 추가로 필요합니다. 어느 시간대의 이용자가 m명 미만이라면, 서버 증설이 필요하지 않습니다. 어느 시간대의 이용자가 n x m명 이상 (n + 1) x m명 미만이라면 최소 n대의 증설된 서버가 운영 중이어야 합니다. 한 번 증설한 서버는 k시간 동안 운영하고 그 이후에는 반납합니다. 예를 들어, k = 5 일 때 10시에 증설한 서버는 10 ~ 15시에만 운영됩니다.

하루 동안 모든 게임 이용자가 게임을 하기 위해 서버를 최소 몇 번 증설해야 하는지 알고 싶습니다. 같은 시간대에 서버를 x대 증설했다면 해당 시간대의 증설 횟수는 x회입니다.

다음은 m = 3, k = 5 일 때의 시간대별 증설된 서버의 수와 증설 횟수 예시입니다.

시각	게임 이용자의 수	증설된 서버의 수	증설 횟수
0 ~ 1	0	0	0
1 ~ 2	2	0	0
2 ~ 3	3	1	1
3 ~ 4	3	1	0
4 ~ 5	1	1	0
5 ~ 6	2	1	0
6 ~ 7	0	1	0
7 ~ 8	0	0	0
8 ~ 9	0	0	0
9 ~ 10	0	0	0
10 ~ 11	4	1	1
11 ~ 12	2	1	0
12 ~ 13	0	1	0
13 ~ 14	6	2	1
14 ~ 15	0	2	0
15 ~ 16	4	1	0
16 ~ 17	2	1	0
17 ~ 18	13	4	3
18 ~ 19	3	3	0
19 ~ 20	5	3	0
20 ~ 21	10	3	0
21 ~ 22	0	3	0
22 ~ 23	1	0	0
23 ~ 24	5	1	1

모든 게임 이용자를 감당하기 위해 최소 7번 서버를 증설해야 하며, 이보다 적은 수의 서버 증설로는 모든 게임 이용자를 감당할 수 없습니다.

0시에서 23시까지의 시간대별 게임 이용자의 수를 나타내는 1차원 정수 배열 players, 서버 한 대로 감당할 수 있는 최대 이용자의 수를 나타내는 정수 m, 서버 한 대가 운영 가능한 시간을 나타내는 정수 k가 주어집니다. 이때, 모든 게임 이용자를 감당하기 위한 최소 서버 증설 횟수를 return 하도록 solution을 완성해 주세요.

---

제한 사항

• players의 길이 = 24
  • 0 ≤ players의 원소 ≤ 1,000
  • players[i]는 i시 ~ i+1시 사이의 게임 이용자의 수를 나타냅니다.
• 1 ≤ m ≤ 1,000
• 1 ≤ k ≤ 24

---

입출력 예

players	m	k	result
[0, 2, 3, 3, 1, 2, 0, 0, 0, 0, 4, 2, 0, 6, 0, 4, 2, 13, 3, 5, 10, 0, 1, 5]	3	5	7
[0, 0, 0, 10, 0, 12, 0, 15, 0, 1, 0, 1, 0, 0, 0, 5, 0, 0, 11, 0, 8, 0, 0, 0]	5	1	11
[0, 0, 0, 0, 0, 2, 0, 0, 0, 1, 0, 5, 0, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1]	1	1	12

---

입출력 예 설명

입출력 예 #1

• 문제의 예시와 같습니다.

입출력 예 #2

• 총 11번 서버를 증설해야 합니다.
  • 3 ~ 4시: 2번
  • 5 ~ 6시: 2번
  • 7 ~ 8시: 3번
  • 15 ~ 16시: 1번
  • 18 ~ 19시: 2번
  • 20 ~ 21시: 1번

입출력 예 #3

• 총 12번 서버를 증설해야 합니다.
  • 5 ~ 6시: 2번
  • 9 ~ 10시: 1번
  • 11 ~ 12시: 5번
  • 13 ~ 14시: 2번
  • 15 ~ 16시: 1번
  • 23 ~ 24시: 1번

---

풀이 과정(오답)

이 문제는 아래와 같이 정리를 하여 진행하고자 했다.

1. 증설할 서버를 담는 변수 생성
2. players 시간별 이용자만큼 로직을 돌리기 위해 아래와 같이 진행
   1. 시간별 이용자와 m을 나누어서 계산 시 증설할 서버 수가 몇 인지 확인하여 증설
   2. k시간 동안 서버가 살아 있어야 하기에 각 서버별 생존 시간을 1씩 감소하는 로직
   3. 서버별 생존시간이 0인 것들을 제거

---

코드(오답)

import java.util.*;
class Solution {
    public int solution(int[] players, int m, int k) {
        int answer = 0;
        
        // 증설한 서버 담는 곳
        List<Integer> expansionserver = new LinkedList<>();
        
        // players 시간별 플레이어 이용자
        for (int i = 0; i < players.length; i++)
        {
            int player = players[i];
            
            // (증설된 서버 < 플레이어 / 증설 기준) 으로 서버 증설
            while (expansionserver.size() < player / m)
            {
                expansionserver.add(k);
                answer++;
            }
            
            // 증설된 서버 만료 처리 방식을 남은 시간 -1씩 감소하는 방법
            for (int j = 0; j < expansionserver.size(); j++)
            {
                int hour = expansionserver.get(j) - 1;
                if (hour >= 0) expansionserver.set(j , hour);
            }
            
            // (증설된 서버 > 플레이어 / 증설 기준) 으로 돌면서 서버 제거
            while (expansionserver.size() > player / m)
            {
                if (expansionserver.get(0) == 0)
                {
                    expansionserver.remove(0);
                }
                else
                {
                    break;
                }
            }
        }
        return answer;
    }
}

---

풀이 과정(정답)

위와 같이 설계하여 진행하였으나 접근 방법이 틀렸었다.

2-a ~ 2-b까지는 맞는데 2-c를 고려하지 않았다.

예를 들어서

players = [10, 10, 10, 10]
m = 5
k = 2

진행하게 된다면 아래와 같이 흘러갈 것이다.

• t=0 → 10명 → 서버 2대 필요 → 증설 2대 (만료 시점: 2시간 후, 즉 t=2)
• t=1 → 10명 → 여전히 서버 2대 필요 → 추가 없음
• t=2 → 기존 2대 만료 → 다시 서버 2대 필요 → 증설 2대
• t=3 → 유지

정답: 총 증설 횟수 = 4회

이러하기에 방법을 아래와 같이 바꾸었다.

1. 증설할 서버를 담는 변수 생성
2. players 시간별 이용자만큼 로직을 돌리기 위해 아래와 같이 진행
   1. 서버별 생존시간이 0인 것들을 제거 (★먼저 처리하도록 변경)
   2. 시간별 이용자와 m을 나누어서 계산 시 증설할 서버 수가 몇 인지 확인하여 증설
   3. k시간 동안 서버가 살아 있어야 하기에 각 서버별 생존 시간을 1씩 감소하는 로직

---

코드(정답)

import java.util.*;
class Solution {
    public int solution(int[] players, int m, int k) {
        int answer = 0;
        
        // 증설한 서버 담는 곳
        List<Integer> expansionserver = new LinkedList<>();
        
        // players 시간별 플레이어 이용자
        for (int i = 0; i < players.length; i++)
        {
            int player = players[i];
            
            // 증설된 서버의 만료시간이 0이면 제거
            while (expansionserver.size() > 0)
            {
                if (expansionserver.get(0) == 0)
                {
                    expansionserver.remove(0);
                }
                else
                {
                    break;
                }
            }
            
            // (증설된 서버 < 플레이어 / 증설 기준) 으로 서버 증설
            while (expansionserver.size() < player / m)
            {
                expansionserver.add(k);
                answer++;
            }
            
            // 증설된 서버 만료 처리 방식을 남은 시간 -1씩 감소하는 방법
            for (int j = 0; j < expansionserver.size(); j++)
            {
                int hour = expansionserver.get(j) - 1;
                if (hour >= 0) expansionserver.set(j , hour);
            }
        }
        return answer;
    }
}

---

다른 사람 풀이

import java.util.*;

class Solution {
    public int solution(int[] players, int m, int k) {
        int count = 0;
        Queue<Integer> active = new LinkedList<>();
        
        // 플레이어는 24명 고정
        for (int i = 0; i < 24; i++) {
            int need = players[i] / m;
						
            // 증설시 담기는 값을 만료 시간으로 했기에 i보다 같거나 작으면 서버 폐쇄
            while (!active.isEmpty() && active.peek() <= i) {
                active.poll();
            }

            int current = active.size();

            // 증설된 서버 < 필요한 서버
            if (current < need) {
                // 새로 증설해야하는 서버 = 필요한 서버 - 증설된 서버
                int newServer = need - current;
                count += newServer;
                // 새로 증설해야하는 서버를 반복문만큼 돌려서 증설
                for (int j = 0; j < newServer; j++) {
                    // i + k로 처리하는 이유!
                    // ★현재 시각 i가 만료 시간으로 처리하기 위함
                    active.offer(i + k);
                }
            }
        }

        return count;
    }
}

다른 사람 코드를 분석하여 주석 달아두었다. 그리고 이렇게도 풀이 가능하다는 것에 대해 많이 배우는 거 같다.