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

작성자: 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
확인 결과: 통과
검증 목적: 최대 이용자 수와 최소 수용 인원에서 불필요한 재증설이 없는지 확인

6. 다른 풀이 방식 검색 및 요약

확인한 공개 풀이들도 시간별 운영 서버 수를 관리하면서, 현재 필요한 서버 수가 운영 중인 수보다 클 때만 부족한 수를 증설하는 방식으로 접근합니다.

• yooputer’s devlog 풀이는 시간별 서버 수를 배열에 기록하고, 증설한 서버가 운영되는 시간 구간에 서버 수를 더하는 방식입니다.
• 프로그래머스 질문 게시판의 TypeScript 풀이는 서버의 증설 시점을 큐에 기록하고 만료 시점에 제거하는 방식입니다.

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

마무리

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