프로그래머스 서버 증설 횟수 풀이: 만료 시점을 관리하는 구현

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

• 문제: 서버 증설 횟수
• 출처: 프로그래머스, 2025 프로그래머스 코드챌린지 2차 예선
• 자체 판단 난이도: Level 2

시간별로 필요한 추가 서버 수를 계산하고, 일정 시간이 지나 반납되는 서버를 관리해야 한다. 서버의 만료 시점을 놓치지 않고 갱신하는 구현이 핵심이므로 Level 2로 판단했다.

1. 문제 요약

기본 서버 1대가 있고, 이용자가 m명 늘어날 때마다 추가 서버 1대가 필요하다. 따라서 한 시간의 이용자가 players[i]명이라면 필요한 추가 서버 수는 다음과 같다.

players[i] // m

한 번 증설한 서버는 k시간 동안 운영된다. 예를 들어 h시에 증설한 서버는 h시부터 h + k시 직전까지 운영되고, h + k시에 반납된다.

하루 24시간 동안 매 시간 필요한 추가 서버 수를 만족시키면서, 증설한 서버의 총 횟수를 최솟값으로 구해야 한다.

2. 문제 해결에 사용되는 알고리즘과 자료구조

상태 전이와 경계 처리

기본 서버 1대는 항상 운영 중이므로 증설이 필요한 서버 수만 계산한다.

예를 들어 m = 3일 때 다음과 같다.

따라서 players[i] // m이 해당 시간에 필요한 추가 서버 수다.

만료 시점 배열

expires[t]에 t시에 반납되는 추가 서버 수를 저장한다.

현재 시간이 hour일 때 다음 순서로 처리한다.

1. expires[hour]만큼 반납하여 현재 운영 중인 추가 서버 수에서 뺀다.
2. 현재 이용자 수로 필요한 추가 서버 수를 계산한다.
3. 현재 운영 중인 서버가 부족하면 부족한 수만큼 증설한다.
4. 새 서버가 hour + k시에 반납되도록 만료 배열에 기록한다.

이미 운영 중인 서버를 다시 증설 횟수에 포함하지 않는 것이 중요하다. 부족한 서버만 추가하면 항상 현재 시간의 조건을 만족하면서 불필요한 증설을 피할 수 있다.

왜 현재 부족한 만큼만 증설할까?

서버는 증설한 시점부터 정확히 k시간 동안만 사용할 수 있다. 현재 필요한 수보다 많이 증설하면 그 초과분도 같은 시각에 만료되므로 이후의 증설을 줄이는 데 유리하지 않다. 반대로 부족한 수만 증설하면 현재 시간의 최소 조건을 만족하고, 각 서버를 가능한 한 필요한 시간 동안만 사용하게 된다.

만료 시점이 만드는 전이

증설 서버는 시작 시각이 아니라 hour + k에 만료된다. 따라서 각 시간에 필요한 전체 서버 수를 다시 배치하는 대신, 현재 시각에 반납될 수를 먼저 빼고 부족한 추가 서버만 증설하면 된다. expires는 상태가 바뀌는 만료 시점만 기록한다.

오답 접근과 반례

현재 필요한 서버 수를 매 시간 새로 증설 횟수로 더하면 이미 운영 중인 서버를 중복 계산한다. 반대로 0시에 1대를 증설하고 k = 3이면 3시에 반납되므로, 3시의 수요가 다시 올라갔을 때만 새로 증설해야 한다.

3. 문제 해결 코드 (Python)

def solution(players, m, k):
    # hour + k 시점까지 접근할 수 있도록 여유 공간을 둡니다.
    expires = [0] * (24 + k + 1)
    active = 0
    answer = 0

    for hour, player_count in enumerate(players):
        # 현재 시각에 운영 기간이 끝난 서버를 반납한다.
        active -= expires[hour]

        needed = player_count // m
        additional = needed - active

        if additional > 0:
            active += additional
            answer += additional
            expires[hour + k] += additional

    return answer

복잡도

players의 길이는 항상 24이므로 시간 복잡도는 O(24), 일반화하면 O(n)이다. 만료 시점 배열의 크기는 O(n + k)이며, 문제 조건에서는 추가 공간 복잡도도 O(24 + k)다.

4. 공식 예제 검증

공식 문제 페이지의 예제 3개를 Python 3.12.4에서 실행했다.

5. 추가 검증 입력·출력

추가 검증 1: 이용자가 없는 경우

입력:
players = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
           0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
m = 3
k = 5

기대 출력: 0
확인 결과: 통과
검증 목적: 기본 서버만으로 충분한 최소 입력 확인

추가 검증 2: 정확히 m명인 경우

입력:
players = [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
           0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
m = 3
k = 5

기대 출력: 1
확인 결과: 통과
검증 목적: 나머지가 0인 경계에서 추가 서버 1대가 필요한지 확인

추가 검증 3: 서버 만료 직후 재증설

입력:
players = [3, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0,
           0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
m = 3
k = 3

기대 출력: 2
확인 결과: 통과
검증 목적: 0시에 증설한 서버가 3시에 반납된 뒤 다시 증설되는지 확인

추가 검증 4: 같은 시간에 여러 대 증설

입력:
players = [10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
           0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
m = 3
k = 5

기대 출력: 3
확인 결과: 통과
검증 목적: 필요한 추가 서버가 1대보다 큰 경우를 확인

추가 검증 5: 최대 이용자와 최소 m

입력:
players = [1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000,
           1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000]
m = 1
k = 24

기대 출력: 1000
확인 결과: 통과
검증 목적: 최대 이용자 수와 최소 수용 인원에서 불필요한 재증설이 없는지 확인

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 증설이 필요 없는 경우와 추가 서버가 필요한 경우를 확인할 수 있다.

assert solution([0] * 24, 3, 5) == 0
assert solution([3] + [0] * 23, 3, 5) == 1

6. 참고 풀이 비교

• yooputer’s devlog 풀이는 시간별 서버 수를 배열에 기록하고, 증설한 서버가 운영되는 시간 구간에 서버 수를 더하는 방식이다.

이 글에서는 하루가 24시간으로 고정되어 있다는 점을 이용해 만료 시점 배열을 사용했다. 구간 전체를 갱신하지 않고 반납 시점만 기록하므로, 서버의 상태 변화가 발생하는 시점을 코드에서 직접 확인하기 쉽다.

마무리

이 문제는 매 시간의 이용자 수만 보는 것이 아니라, 이전에 증설한 서버가 아직 운영 중인지 함께 확인해야 한다. 현재 시각에 만료되는 서버를 먼저 반납하고 부족한 수만 증설하면 최소 증설 횟수를 구할 수 있다.