프로그래머스

프로그래머스 기지국 설치 풀이: 빈 구간 길이 계산 그리디

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

0. 문제 링크와 출처

  • 문제: 기지국 설치
  • 출처: 프로그래머스, Summer/Winter Coding(~2018)
  • 자체 판단 난이도: Level 3

아파트 수가 최대 2억이므로 각 아파트를 직접 확인할 수 없다. 기존 기지국이 커버하는 구간 사이의 빈 구간만 계산하고, 구간 길이에서 필요한 기지국 수를 바로 구해야 한다. 왼쪽·오른쪽 경계와 올림 나눗셈을 정확히 처리해야 하므로 Level 3으로 판단했다.

1. 문제 요약

아파트 N개가 일렬로 있고, stations에는 현재 기지국이 설치된 아파트 번호가 오름차순으로 주어진다. 기지국이 설치된 위치에서 양쪽으로 W만큼 전파가 전달될 때, 모든 아파트가 전파를 받을 수 있도록 추가로 설치해야 하는 기지국의 최소 개수를 구한다.

기지국 하나가 커버하는 아파트 구간은 다음과 같다.

station - W ~ station + W

따라서 기지국 하나가 커버하는 연속된 아파트 수는 2 * W + 1이다.

제한 조건에서 N은 최대 200,000,000, stations의 길이는 최대 10,000이다. 따라서 아파트 번호마다 전파 여부를 배열에 저장하거나 모든 아파트를 순회하는 방식은 사용할 수 없다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

그리디 선택 기준

기존 기지국을 왼쪽부터 확인하면서 아직 처리하지 않은 첫 아파트 위치를 start로 관리한다. 현재 기지국의 전파 범위가 [station - W, station + W]라면, start부터 station - W - 1까지가 전파를 받지 못하는 빈 구간이다.

빈 구간의 길이가 length일 때 필요한 기지국 수는 기지국 하나의 커버 길이로 나눈 올림이다.

필요한 기지국 수 = ceil(length / (2 * W + 1))

Python에서 올림 나눗셈은 다음과 같이 정수 연산으로 표현할 수 있다.

(length + coverage - 1) // coverage

현재 기지국의 오른쪽 끝까지는 이미 전파가 전달되므로, 다음에 확인할 시작 위치를 station + W + 1로 이동한다. 모든 기존 기지국을 확인한 뒤 N까지 남은 구간도 같은 방식으로 처리한다.

빈 구간마다 필요한 기지국 수를 계산하기

이 문제의 답은 각 아파트의 상태가 아니라 기존 기지국 사이의 빈 구간 길이만으로 결정된다. 빈 구간 안에 새 기지국을 설치할 때는 기지국 하나가 최대 2 * W + 1개의 연속된 아파트를 커버할 수 있으므로, 구간을 이 길이 단위로 나눈 올림만큼 설치하면 된다.

stations가 오름차순이므로 왼쪽 빈 구간을 처리한 뒤 현재 기지국의 오른쪽 끝 다음으로 start를 이동하면 이전 구간을 다시 볼 필요가 없다. 또한 기존 기지국의 범위가 겹치는 경우에는 start < left일 때만 빈 구간을 계산하므로 음수 길이를 더하지 않는다.

상태 전이와 경계 처리

각 기존 기지국에 대해 다음 순서로 처리한다.

  1. left = station - W, right = station + W를 계산한다.
  2. start < left이면 [start, left - 1]의 길이를 계산한다.
  3. 빈 구간에 필요한 기지국 수를 올림 나눗셈으로 더한다.
  4. 다음 미확인 위치를 right + 1로 이동한다.

첫 번째 기지국보다 왼쪽에 빈 구간이 있으면 start = 1에서 시작해 처리한다. 마지막 기지국의 오른쪽도 start <= N이면 [start, N]을 처리한다. 기지국의 전파 범위가 아파트 범위를 넘어가더라도 start > N이 되므로 마지막 처리를 건너뛸 수 있다.

그리디 선택이 최적인 이유

전파가 닿지 않는 하나의 연속 구간은 기존 기지국의 전파가 닿지 않는 독립된 범위다. 새 기지국 하나가 커버할 수 있는 아파트 수는 최대 2 * W + 1이므로, 길이가 length인 구간을 덮는 데 필요한 최소 개수는 어떤 배치에서도 ceil(length / coverage)보다 작을 수 없다.

이 개수만큼 기지국을 빈 구간 안에 연속으로 배치하면 각 기지국의 범위가 이어지도록 만들 수 있다. 따라서 각 빈 구간에서 이 하한을 정확히 달성하고, 구간별 결과를 더한 값이 전체 최솟값이다.

오답 접근과 반례

N개의 아파트마다 전파 여부를 저장한 배열을 만들면 N = 200,000,000에서 과도한 메모리와 시간이 필요하다. 문제에서 stations의 개수는 훨씬 작으므로, 기지국 사이의 빈 구간만 계산해야 한다.

또한 빈 구간 길이를 나눈 몫만 사용하면 나머지가 있는 경우 기지국 하나를 빠뜨린다.

빈 구간 길이 = 6
W = 2
기지국 하나의 커버 길이 = 5

6 // 5 = 1이지만 기지국 하나로는 6개 아파트를 모두 덮을 수 없다. 올림 나눗셈을 사용해 2개를 계산해야 한다.

기존 기지국의 범위를 만날 때마다 무조건 빈 구간을 계산하는 것도 위험하다. 범위가 겹치면 station - W가 현재 start보다 왼쪽일 수 있으므로, start < left인 경우에만 길이를 계산해야 한다.

시간·공간 복잡도

stations를 한 번 순회하므로 시간 복잡도는 O(k)다. 여기서 k는 기존 기지국의 개수이며, 입력 조건상 최대 10,000이다. 아파트 수 N과 관계없이 처리한다.

추가 배열 없이 위치와 개수 변수만 사용하므로 공간 복잡도는 O(1)이다.

3. 문제 해결 코드 (Python)

def solution(n, stations, w):
    coverage = 2 * w + 1
    answer = 0
    start = 1

    for station in stations:
        left = station - w
        right = station + w

        if start < left:
            length = left - start
            answer += (length + coverage - 1) // coverage

        start = right + 1

    if start <= n:
        length = n - start + 1
        answer += (length + coverage - 1) // coverage

    return answer

start는 아직 전파 커버 여부를 처리하지 않은 첫 아파트다. 기존 기지국이 커버하는 오른쪽 끝 다음으로 start를 옮기기 때문에, 기존 기지국이 서로 겹쳐도 이미 처리한 구간을 중복 계산하지 않는다.

문제에서 stations는 오름차순이라고 보장하므로 별도의 정렬도 필요하지 않다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 기존 기지국 사이의 빈 구간 계산을 확인할 수 있다.

assert solution(11, [4, 11], 1) == 3
assert solution(16, [9], 2) == 3

4. 공식 예제와 추가 검증

공식 예제와 양끝·중앙·대규모 입력을 Python 코드로 실행해 확인했다.

공식 예제

입력 기대 출력 확인 결과
N = 11, stations = [4, 11], W = 1 3 통과
N = 16, stations = [9], W = 2 3 통과

추가 검증 1: 모든 아파트가 기존 기지국으로 커버되는 경우

입력: N = 1, stations = [1], W = 1
기대 출력: 0
확인 결과: 통과
검증 목적: 추가 설치가 필요 없는 최소 입력 확인

추가 검증 2: 기존 기지국 양쪽에 빈 구간이 있는 경우

입력: N = 5, stations = [3], W = 1
기대 출력: 2
확인 결과: 통과
검증 목적: 중앙 기지국의 왼쪽과 오른쪽 빈 구간을 각각 계산하는지 확인

추가 검증 3: 전파 범위가 겹치는 기존 기지국

입력: N = 10, stations = [1, 10], W = 1
기대 출력: 2
확인 결과: 통과
검증 목적: 양끝 기지국 사이의 빈 구간 길이 6을 커버 길이 3으로 올림 계산하는지 확인

추가 검증 4: 제한에 가까운 아파트 수

입력: N = 200000000, stations = [100000000], W = 10000
기대 출력: 10000
확인 결과: 통과
검증 목적: 아파트 전체를 순회하지 않고 큰 N을 구간 계산만으로 처리하는지 확인

5. 다른 풀이 방식 검색 및 비교

  • 프로그래머스 공식 문제는 기존 기지국의 범위와 추가 설치 개수의 최솟값을 정의한다.
  • Bellroute의 Python 풀이는 기지국 사이의 전파 미도달 구간을 계산하고, 기지국 하나의 커버 길이로 나누어 필요한 개수를 구하는 접근을 설명한다.

두 접근 모두 아파트 전체를 배열로 만들지 않고 빈 구간의 길이만 계산한다는 점이 같다. 이 글에서는 start를 아직 처리하지 않은 첫 위치로 정의하고, 현재 기지국의 left와 비교해 빈 구간 여부를 먼저 판정하는 방식으로 겹치는 전파 범위와 양끝 경계를 명확히 처리했다.

마무리

기지국 설치는 매우 큰 아파트 수를 직접 순회하지 않고, 기존 기지국 사이에서 전파가 닿지 않는 구간만 세어 해결하는 그리디 문제다. 기지국 하나의 커버 길이 2 * W + 1을 구한 뒤 각 빈 구간에 대해 올림 나눗셈을 적용하면 O(k) 시간과 O(1) 공간으로 최소 추가 설치 개수를 계산할 수 있다.

#그리디#프로그래머스#난이도 3