문제 출처 : 프로그래머스
난이도 : Level 3
문제 요약
아파트가 1번부터 N번까지 일렬로 배치되어 있고, 일부 아파트에는 이미 기지국이 설치되어 있다.
각 기지국은 자신의 위치를 기준으로 왼쪽과 오른쪽으로 W만큼 전파를 전달할 수 있다.
모든 아파트에 전파가 전달되도록 기지국을 추가로 설치할 때, 필요한 기지국 개수의 최솟값을 구하는 문제다.
처음에 헷갈렸던 점
문제 설명에 4G와 5G가 등장해서 통신 방식에 따른 차이를 고려해야 하는 문제라고 생각했다.
하지만 실제 풀이에서는 4G와 5G가 중요하지 않았다.
문제를 풀기 위해 필요한 값은 다음 세 가지뿐이었다.
- 전체 아파트 개수
N - 현재 기지국이 설치된 위치
stations - 기지국의 전파 도달 거리
W
결국 핵심은 기존 기지국이 전파를 전달하지 못하는 빈 구간의 길이를 구하는 것이었다.
처음 생각한 풀이
기존 기지국이 담당하는 범위를 [시작 위치, 끝 위치] 형태로 저장했다.
예를 들어 기지국의 위치가 4이고 W = 1이라면 전파 범위는 다음과 같다.
[3, 5]여러 기지국의 전파 범위를 구한 뒤, 각 전파 범위 사이에 존재하는 빈 구간의 길이를 계산했다.
import math
def solution(n, stations, w):
# 기지국 하나가 담당할 수 있는 아파트 수
tower_space = 2 * w + 1
# 앞쪽 경계 처리를 위한 가상의 범위
ranges = [[-200000000, 0]]
for loc in stations:
start = loc - w
end = loc + w
# 전파 범위의 끝이 N을 넘어가지 않도록 처리
end = min(end, n)
ranges.append([start, end])
# 뒤쪽 경계 처리를 위한 가상의 범위
ranges.append([n + 1, 200000000])
cur = 0
uninstalled_spaces = []
for i in range(1, len(ranges)):
start, end = ranges[i]
# 이전 전파 범위와 현재 전파 범위 사이의 빈 공간
uninstalled_spaces.append(start - cur - 1)
cur = end
answer = 0
for space in uninstalled_spaces:
answer += math.ceil(space / tower_space)
return answer내 풀이의 핵심 아이디어
기지국 하나가 전파를 전달할 수 있는 전체 아파트 수는 다음과 같다.
2 * w + 1기지국이 설치된 현재 위치를 포함하고, 왼쪽으로 w개, 오른쪽으로 w개의 아파트에 전파를 전달하기 때문이다.
예를 들어 W = 2라면 기지국 하나가 담당할 수 있는 아파트 수는 총 5개다.
[왼쪽 2개] [기지국] [오른쪽 2개]따라서 전파가 닿지 않는 빈 구간의 길이가 space라면 필요한 기지국 수는 다음과 같이 구할 수 있다.
math.ceil(space / (2 * w + 1))빈 공간이 조금이라도 남으면 기지국을 한 대 더 설치해야 하기 때문에 올림 계산이 필요하다.
빈 구간 계산하기
기존 기지국의 전파 범위가 다음과 같다고 가정하자.
ranges = [
[-200000000, 0],
[3, 5],
[10, 12],
[n + 1, 200000000]
]첫 번째 실제 기지국은 3번부터 5번 아파트까지 전파를 전달한다.
따라서 첫 번째 기지국 이전의 빈 공간은 다음과 같다.
3 - 0 - 1
# 2즉, 1번과 2번 아파트가 빈 구간이다.
두 기지국 사이의 빈 공간은 다음과 같다.
10 - 5 - 1
# 4즉, 6번부터 9번까지 총 4개의 아파트가 빈 구간이다.
이러한 방식으로 각 전파 범위 사이의 간격을 계산했다.
내 풀이에서 잘한 점
1. 모든 아파트를 하나씩 확인하지 않았다
처음에는 1번부터 N번 아파트까지 하나씩 순회하며 전파 수신 여부를 확인할 수도 있다.
하지만 이 문제에서 필요한 것은 각 아파트의 개별 상태가 아니라, 기존 기지국 사이에 생기는 연속된 빈 구간의 길이다.
따라서 전체 아파트를 순회하지 않고 기존 기지국의 개수만큼만 확인했다.
N의 최댓값은 200,000,000이므로 모든 아파트를 직접 확인하는 방법은 비효율적이다.
2. 문제를 구간 단위로 바라봤다
전파가 닿지 않는 아파트를 하나씩 저장하지 않고, 연속된 빈 공간을 하나의 구간으로 처리했다.
예를 들어 다음과 같은 빈 공간이 있다고 하자.
6, 7, 8, 9이 아파트들을 각각 확인할 필요 없이 빈 구간의 길이가 4라는 사실만 알면 된다.
space = 4연속된 영역에서는 각 원소보다 구간의 시작점, 끝점, 길이를 이용하는 것이 더 효율적일 수 있다.
3. 기지국 하나의 최대 담당 범위를 이용했다
문제에서는 설치해야 하는 기지국 수의 최솟값을 구해야 한다.
따라서 기지국 하나를 설치할 때마다 최대한 많은 아파트를 담당하도록 해야 한다.
기지국 하나의 최대 담당 범위는 다음과 같다.
tower_space = 2 * w + 1각 빈 구간의 길이를 tower_space로 나누면 필요한 최소 기지국 수를 계산할 수 있다.
4. 앞쪽과 뒤쪽 구간을 같은 방식으로 처리했다
첫 번째 기지국 이전의 구간과 마지막 기지국 이후의 구간은 별도로 처리하기 쉽다.
내 풀이에서는 가상의 범위를 앞뒤에 추가해 모든 구간을 동일한 반복문 안에서 계산했다.
ranges = [[-200000000, 0]]
ranges.append([n + 1, 200000000])200000000은 문제에서 주어진 N의 최댓값이다.
따라서 의미 없이 정한 임의의 숫자는 아니며, 문제의 범위를 기준으로 설정한 값이다.
내 풀이에서 아쉬운 점
풀이의 핵심 아이디어와 시간복잡도는 적절했지만, 중간 리스트를 사용하면서 구현이 조금 복잡해졌다.
1. 중간 리스트를 여러 번 만들었다
내 풀이에서는 다음 두 개의 리스트를 만들었다.
ranges
uninstalled_spaces먼저 기존 기지국의 전파 범위를 ranges에 저장했다.
그다음 ranges를 다시 순회하면서 빈 구간의 길이를 uninstalled_spaces에 저장했다.
마지막으로 uninstalled_spaces를 다시 순회하며 필요한 기지국 수를 계산했다.
stations
→ ranges 생성
→ uninstalled_spaces 생성
→ answer 계산하지만 기존 기지국을 확인하는 순간 빈 구간의 길이를 계산하고 바로 정답에 더할 수 있다.
따라서 중간 계산 결과를 모두 리스트에 저장할 필요는 없다.
2. 가상의 범위 전체 값은 실제 계산에 사용되지 않는다
경계 처리를 위해 다음과 같은 가상의 범위를 추가했다.
[-200000000, 0]
[n + 1, 200000000]200000000은 문제의 범위에 존재하는 값이므로 임의의 숫자는 아니다.
다만 실제 계산에서 필요한 값은 앞쪽 범위의 끝인 0과 뒤쪽 범위의 시작인 n + 1뿐이다.
즉, 다음과 같이 작성해도 같은 결과를 얻을 수 있다.
ranges = [[0, 0]]
ranges.append([n + 1, n + 1])가상의 범위를 사용하는 방식이 틀린 것은 아니지만, 필요한 값만 사용하면 코드의 의도를 조금 더 명확하게 표현할 수 있다.
3. 전파 범위가 겹치면 빈 구간 길이가 음수가 될 수 있다
빈 구간의 길이는 다음과 같이 계산했다.
space = start - cur - 1두 기지국의 전파 범위가 겹치는 경우에는 실제 빈 공간이 없지만 space가 음수가 될 수 있다.
예를 들어 이전 기지국의 전파 범위가 [3, 7]이고 다음 기지국의 전파 범위가 [6, 10]이라고 하자.
space = 6 - 7 - 1
# -2실제로는 두 전파 범위 사이에 빈 아파트가 없다.
내 코드에서는 음수 값을 그대로 다음 계산에 사용한다.
math.ceil(space / tower_space)기지국의 위치가 중복되지 않고 오름차순으로 주어진다는 조건에서는 음수 값의 절댓값이 tower_space보다 작다.
따라서 계산 결과는 0이 되고 정답에는 영향을 주지 않는다.
즉, 현재 코드도 정상적으로 동작한다.
다만 다음과 같이 빈 공간이 존재하는 경우만 계산하면 코드의 의도가 더 명확해진다.
if space > 0:
answer += math.ceil(space / tower_space)현재 구현이 틀린 것은 아니지만, 조건을 명시하면 빈 구간이 없는 경우 기지국을 추가하지 않는다는 의미를 더 쉽게 파악할 수 있다.
중간 리스트를 사용하지 않는 더 나은 풀이
내 풀이와 핵심 아이디어는 같지만, 중간 리스트를 만들지 않고 포인터 하나로 처리할 수 있다.
포인터는 다음 위치를 의미한다.
positionposition은 아직 전파가 닿지 않은 첫 번째 아파트다.
기존 기지국을 순서대로 확인하면서 다음 과정을 반복한다.
- 현재 기지국의 전파 시작 위치를 구한다.
position부터 기존 기지국의 전파 시작 전까지의 빈 구간을 구한다.- 빈 구간에 필요한 기지국 수를 정답에 더한다.
position을 현재 기지국의 전파 범위 다음 위치로 이동한다.- 모든 기지국을 확인한 뒤 마지막 남은 구간을 처리한다.
더 나은 풀이 코드
def solution(n, stations, w):
answer = 0
# 기지국 하나가 담당할 수 있는 아파트 수
coverage = 2 * w + 1
# 아직 전파가 닿지 않은 첫 번째 아파트
position = 1
for station in stations:
# 현재 기지국의 전파 시작 위치
start = station - w
# position부터 현재 기지국의 전파 시작 전까지의 빈 구간
gap = start - position
if gap > 0:
answer += (gap + coverage - 1) // coverage
# 현재 기지국의 전파 범위 다음 위치로 이동
position = max(position, station + w + 1)
# 마지막 기지국 이후에 남은 빈 구간
if position <= n:
gap = n - position + 1
answer += (gap + coverage - 1) // coverage
return answer더 나은 풀이 동작 과정
예를 들어 다음과 같은 입력이 있다고 하자.
n = 11
stations = [4, 11]
w = 1기지국 하나가 담당할 수 있는 범위는 다음과 같다.
coverage = 2 * 1 + 1
# 3처음 아직 전파가 닿지 않은 아파트는 1번이다.
position = 1첫 번째 기지국의 위치는 4번이다.
이 기지국은 3번부터 5번까지 전파를 전달한다.
start = 4 - 1
# 3현재 position은 1이므로 빈 구간은 1번부터 2번까지다.
gap = 3 - 1
# 2기지국 한 대가 최대 3개의 아파트를 담당할 수 있으므로 기지국 한 대가 필요하다.
answer += ceil(2 / 3)
# 1그다음 position을 기존 기지국의 전파 범위 다음 위치로 이동시킨다.
position = 4 + 1 + 1
# 6두 번째 기지국은 11번에 설치되어 있다.
이 기지국은 10번부터 11번까지 전파를 전달한다.
start = 11 - 1
# 10현재 position은 6이므로 빈 구간은 6번부터 9번까지다.
gap = 10 - 6
# 4기지국 한 대가 3개의 아파트를 담당하므로 총 2대가 필요하다.
answer += ceil(4 / 3)
# 2따라서 최종적으로 설치해야 하는 기지국 수는 3개다.
올림 나눗셈
내 풀이에서는 math.ceil()을 사용했다.
math.ceil(gap / coverage)더 나은 풀이에서는 다음과 같은 정수 나눗셈을 사용했다.
(gap + coverage - 1) // coverage두 계산은 같은 의미다.
예를 들어 빈 구간이 4칸이고 기지국 하나가 3칸을 담당한다면 다음과 같다.
(4 + 3 - 1) // 36 // 32기지국 한 대를 설치하면 한 칸이 남기 때문에 총 2대가 필요하다.
이처럼 나머지가 하나라도 존재하면 하나를 더 사용해야 하는 상황에서는 올림 나눗셈을 사용할 수 있다.
풀이 비교
| 구분 | 내 풀이 | 더 나은 풀이 |
|---|---|---|
| 핵심 아이디어 | 빈 구간의 길이 계산 | 빈 구간의 길이 계산 |
| 시간복잡도 | O(K) | O(K) |
| 공간복잡도 | O(K) | O(1) |
| 전파 범위 리스트 | 사용 | 사용하지 않음 |
| 빈 구간 리스트 | 사용 | 사용하지 않음 |
| 경계 처리 | 가상의 범위 추가 | 포인터와 마지막 구간 직접 처리 |
| 범위 중첩 처리 | 올림 결과가 0이 되는 성질 이용 | max()로 명시적으로 처리 |
| 특징 | 계산 과정이 단계적으로 보임 | 더 간결하고 메모리 효율적임 |
K는 현재 설치되어 있는 기지국의 개수다.
두 풀이 모두 기존 기지국을 한 번씩 확인하기 때문에 시간복잡도는 O(K)다.
내 풀이에서는 ranges와 uninstalled_spaces 리스트를 만들기 때문에 O(K)의 추가 공간이 필요하다.
더 나은 풀이에서는 포인터와 몇 개의 변수만 사용하기 때문에 공간복잡도는 O(1)이다.
이 문제를 통해 배운 점
1. 전체를 직접 순회하지 않고 구간으로 생각하기
처음에는 각 아파트에 전파가 닿는지 하나씩 확인해야 할 것처럼 보였다.
하지만 N의 최댓값은 200,000,000이므로 모든 아파트를 직접 순회하는 것은 적절하지 않다.
실제로 필요한 것은 각 아파트의 상태가 아니라 전파가 닿지 않는 연속 구간의 길이였다.
이 문제를 통해 개별 원소를 하나씩 확인하기보다 연속된 영역을 구간 단위로 바라보는 방법을 배울 수 있었다.
2. 최소 개수 문제에서는 하나가 담당할 수 있는 최대 범위를 확인하기
기지국을 최소한으로 설치하려면 기지국 하나를 설치할 때마다 최대한 많은 아파트를 담당하게 해야 한다.
기지국 하나가 담당할 수 있는 최대 범위는 다음과 같다.
2 * w + 1따라서 빈 구간의 길이를 최대 담당 범위로 나누면 필요한 최소 기지국 수를 구할 수 있었다.
3. 연속된 영역에서는 길이만으로 계산할 수 있다
빈 공간이 다음과 같다고 하자.
6, 7, 8, 9각 아파트를 리스트에 저장하거나 하나씩 검사할 필요는 없다.
빈 구간의 길이가 4라는 정보만 있으면 필요한 기지국 수를 계산할 수 있다.
gap = 4연속된 범위를 다루는 문제에서는 원소 자체보다 시작 위치, 끝 위치, 구간의 길이가 중요할 수 있다는 것을 배웠다.
4. 중간 결과를 모두 저장할 필요는 없다
내 풀이에서는 전파 범위와 빈 구간을 리스트에 저장한 뒤 다시 순회했다.
하지만 더 나은 풀이에서는 아직 전파가 닿지 않은 첫 번째 위치만 기억하면 된다.
position = 1기존 기지국을 확인할 때마다 position을 다음 미커버 위치로 갱신하면 중간 결과를 저장하지 않고도 문제를 해결할 수 있다.
이 문제를 통해 현재 상태를 나타내는 포인터 하나만으로 계산을 이어가는 방법을 배울 수 있었다.
5. 구간 문제에서는 양 끝 경계를 주의해야 한다
기지국 사이의 빈 구간만 생각하면 다음 두 구간을 놓치기 쉽다.
- 첫 번째 기지국 이전
- 마지막 기지국 이후
구간 문제에서는 중간 구간뿐만 아니라 시작 경계와 끝 경계도 반드시 확인해야 한다.
내 풀이에서는 가상의 범위를 추가해서 처리했고, 더 나은 풀이에서는 시작 포인터와 마지막 조건문으로 처리했다.
6. 전파 범위가 겹치는 상황도 고려해야 한다
기존 기지국의 전파 범위는 서로 겹칠 수 있다.
이 경우 다음 미커버 위치를 단순히 현재 기지국의 끝으로 변경하면, 이미 더 넓게 커버된 범위가 뒤로 이동할 수 있다.
따라서 더 나은 풀이에서는 다음과 같이 처리한다.
position = max(position, station + w + 1)현재까지 계산된 미커버 위치와 새로운 기지국의 전파 범위 다음 위치 중 더 큰 값을 선택한다.
이를 통해 전파 범위가 겹치는 경우에도 포인터가 뒤로 이동하지 않도록 할 수 있다.
7. 남는 공간이 하나라도 있으면 올림 나눗셈을 사용한다
빈 구간의 길이가 기지국의 최대 담당 범위로 정확히 나누어떨어지지 않으면 기지국 한 대를 추가로 설치해야 한다.
math.ceil(gap / coverage)또는 다음과 같이 정수 연산으로 표현할 수 있다.
(gap + coverage - 1) // coverage이처럼 나머지가 존재할 때 하나를 추가해야 하는 문제에서는 올림 나눗셈을 사용할 수 있다.
회고
처음에는 기존 기지국의 전파 범위를 모두 리스트에 저장한 뒤, 각 범위 사이의 빈 공간을 계산했다.
핵심 아이디어와 시간복잡도는 적절했지만, ranges와 uninstalled_spaces라는 중간 리스트를 사용하면서 구현이 조금 복잡해졌다.
이후 아직 전파가 닿지 않은 첫 번째 아파트를 포인터로 관리하면 중간 결과를 저장하지 않고도 같은 계산을 수행할 수 있다는 것을 알게 되었다.
내 풀이와 더 나은 풀이 모두 전파가 닿지 않는 빈 구간의 길이를 구한 뒤, 기지국 하나가 담당할 수 있는 최대 범위로 올림 나눗셈한다는 핵심 아이디어는 같다.
다만 더 나은 풀이에서는 포인터 하나만 사용하기 때문에 공간복잡도를 O(K)에서 O(1)로 줄일 수 있고, 코드도 더 간결하게 작성할 수 있다.
개별 아파트를 하나씩 확인하는 문제가 아니라, 전파가 닿지 않는 연속된 빈 구간의 길이를 구하고 기지국 하나의 최대 커버 범위로 나누는 구간 그리디 문제였다.
