[ 프로그래머스 ] 기지국 설치 (C++)

프로그래머스

 

난이도 : Level 3 
알고리즘 유형 : 그리디, 수학 
풀이 시간 : 37분 

문제 풀이 

N개의 아파트가 일렬로 쭉 늘어서 있고, 원래 있던 기지국에 다른 기지국을 추가하여 모든 아파트를 커버해야 한다. 모든 아파트를 커버하기 위한 추가 기지국 개수의 최솟값을 구하자.

 

문제의 제한사항을 살펴보면 일단 $N ≤ 200000000$이기 때문에 배열을 사용하여 커버 여부를 살핀다면 메모리 초과가 발생할 뿐더러 시간초과 역시 발생한다. 다행이도 $stations의 크기 ≤ 10000$으로 주어졌기 때문에 해당 문제는 stations을 순회하는 방식으로 해결해야 한다.

 

한 기지국이 커버할 수 있는 범위 $W$가 주어진다. 기지국이 설치된 인덱스 포함 양쪽으로 W만큼 커버가 가능하고, 커버 범위를 수식으로 나타내면 $total_w = 2 * W + 1$로 쓸 수 있다.

 

이전에 아파트를 하나하나 살펴보는 것은 시간 및 공간 제한에 걸린다고 하였다. 어라 ? 문제를 다시 살펴보면 기지국이 어디에 설치되어야 하는지는 상관없고, 단순히 설치된 기지국 개수의 최솟값만 구하면 된다 ! 이 말은 즉슨 수학적으로 문제를 풀어나갈 수 있다.

또한, stations 배열이 오름차순으로 정렬되어 주어진다고 했기 때문에 이를 다시 분석해보면 사전에 설치된 기지국이 커버하는 왼쪽 끝 인덱스와 이전에 커버되지 않은 인덱스 간 차이를 커버할 수 있는 기지국의 개수를 answer에 더하기만 하면 된다.

왜냐하면 $W$가 고정된 길이이기 때문에, `stations[i]의 left`는 `stations[i - 1]의 left`보다 절대 작아질 수 없다.

 

따라서, 우리는 현재 커버되고 있는 인덱스를 지정해준 뒤, 만약 이미 설치된 기지국의 left - idx 가 존재한다면, 해당 범위를 커버할 기지국의 개수를 계산해주어 answer에 더해주면 된다.

 

여기서, 몇 개의 기지국이 사용되었는지 어떻게 계산하지? 라는 생각이 들 수도 있다. 이를 해결하기 위해서는 올림 계산을 사용할 수 있다. 본인은 `answer += (len + total_w - 1) / total_w;` 식을 사용하여서 올림을 계산해주었는데, 원리는 다음과 같다.

 

int형을 나누는 것이기 때문에 정수 나눗셈이므로 소수점을 버리게 된다. 하지만 우리는 올림을 진행해야 하기 때문에, 해당 길이에 나누는 값인 `total_w`를 더해준 다음, -1을 해주어 나머지가 존재하는 경우 자동으로 올림이 적용되도록 하였다.

예시를 들어서 확인해보자. 

• 예: len  = 10, total_w = 5

$(10 + 5 - 1) / 5 = 14 / 5 = 2$

• 예: len  = 6, total_w = 5

$(6 + 5 - 1) / 5 = 10 / 5 = 2$

 

이외에도 기본적인 방식으로 if - else 문을 사용한 계산법이 있다. 이 방법은 모듈러 연산을 사용하여 나머지가 있는 경우라면 나눈 결과 + 1을 진행해주고, 나머지가 없다면 단순히 나눗셈만을 진행해주는 방법을 사용한다. 해당 방법이 가독성은 더 좋다.

if (len % total_w != 0) {
    answer += (len / total_w) + 1;
} else {
    answer += (len / total_w);
}

 

이렇게 문제를 풀어낼 수 있다.

해당 문제의 시간복잡도를 살펴보면 stations에 대한 순회를 진행하고 있기 때문에 $O(stations의 길이)$로 해결할 수 있다.

 

코드

/*
5g 기지국을 최소로 설치하면서 모든 아파트에 전파를 전달하려고 한다.
초기 기지국이 주어지고, 추가로 몇 개를 더 지어야하는지에 대한 최솟값을 구하자

풀이 : 이미 설치된 기지국을 기준으로 나누어서 체크해야함
근데, 겹치는 부분이 있는지는 체크해야함 (그 부분에는 설치 안해도 된다)
- 왼쪽만 겹치게 되어있음 = 마지막 녀석과 비교하기

*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int solution(int n, vector<int> stations, int w) {
    int answer = 0;
    int total_w = 2 * w + 1;

    int idx = 1;
    for (int station : stations) {
        int left = max(1, station - w);
        int right = min(n, station + w);

        // 현재 커버되지 않은 구간 길이
        if (idx < left) {
            int len = left - idx;
            cout << len << '\n';
            answer += (len + total_w - 1) / total_w;
        }
        idx = right + 1;
    }

    // 마지막 남은 구간 처리
    if (idx <= n) {
        int len = n - idx + 1;
        answer += (len + total_w - 1) / total_w;
    }

    return answer;
}

배운 점 

해당 문제는 어떻게보면 수학적으로 접근해야 했던 문제이다. 

N의 범위를 보고 이분탐색을 생각했지만 W가 고정되어있다는 점, 이전 계산 결과가 다음 계산에 영향을 미치지 않는다는점 등 문제를 깊게 분석하는 것이 선행되어야 한다고 생각하였다. 또한, 다양한 알고리즘 문제를 더 풀어봐야 할 것 같다는 생각을 했다 !