출처 : 프로그래머스
난이도 : Level 2
문제 설명
당신은 온라인 게임을 운영하고 있습니다. 같은 시간대에 게임을 이용하는 사람이 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
- 1 ≤ m ≤ 1,000
- 1 ≤ k ≤ 24
테스트 케이스 구성 안내
아래는 테스트 케이스 구성을 나타냅니다. 각 그룹 내의 테스트 케이스를 모두 통과하면 해당 그룹에 할당된 점수를 획득할 수 있습니다.
| 그룹 | 총점 | 추가 제한 사항 |
| #1 | 5% | m = 1, k = 1 |
| #2 | 7% | k = 1 |
| #3 | 88% | 추가 제한 사항 없음 |
입출력 예
| 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
- 총 12번 서버를 증설해야 합니다.
----------------------------------------------------------------------------------------------------------------------------
문제 해독
온라인 게임 진행중 서버의 개수가 부족해지면 추가 서버를 증설하여 유저가 플레이할 수 있게 지원합니다.
문제접근
매시각마다 만료되는 서버, 플레이어 수 대비 현재 서버의 수, 서버가 부족할시 (현재 시간 + k)에 종료되는 서버를 현재 시간에 필요한 만큼 증설 합니다.(단, 서버 대비 사용자가 적을 경우 추가적인 연산은 없습니다.)
필요 변수 리스트
- 서버 생성 횟수
- 현재 서버의 수
- 큐(현재 서버의 만료시간을 가지고 있는 큐)
필요 알고리즘
- 시뮬레이션
- 그리디
using System;
using System.Collections.Generic;
public class Solution {
public int solution(int[] players, int m, int k) {
int createServerCount = 0;
int liveServer = 0;
Queue<int> serverEndTimes = new Queue<int>();
for (int i = 0; i < players.Length; i++) {
while (serverEndTimes.Count > 0 && serverEndTimes.Peek() == i) {
serverEndTimes.Dequeue();
liveServer--;
}
int needServer = players[i] / m;
if (needServer > liveServer) {
int add = needServer - liveServer;
createServerCount += add;
liveServer += add;
for (int j = 0; j < add; j++) {
serverEndTimes.Enqueue(i + k);
}
}
}
return createServerCount;
}
}