목차
1. 문제 설명
2. 접근 방식
3. 코드
4. 시간 복잡도 및 공간 복잡도 계산
1. 문제 설명
https://school.programmers.co.kr/learn/courses/30/lessons/389479
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr


문제 핵심 조건은 아래와 같다.
- 같은 시간대에 게임을 이용하는 사람이 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)와 같다.
'Problem Solving > Programmers' 카테고리의 다른 글
| [Algorithm] 경주로 건설 (0) | 2025.09.09 |
|---|---|
| [Algorithm] 여행경로 (1) | 2025.09.05 |
| [SQL] 멸종위기의 대장균 찾기 문제 풀이 (0) | 2025.03.07 |
| [SQL] 대장균들의 자식의 수 구하기 문제 풀이 (4) | 2025.03.05 |
| [SQL] 특정 형질을 가지는 대장균 찾기 문제 풀이 (1) | 2025.03.04 |