[프로그래머스 lv3] 기지국 설치 풀이

해설

n의 최대 범위가 200000000 이므로 배열을 만들어 일일이 5G 영역을 체크하기엔 시간복잡도가 크다.

해서, 배열을 사용하지 않는 방법을 강구해야 하는데, 일단 주어진 stations 를 이용하여 이미 5G의 영향 아래에 있는 영역을 구해보자.

 

1) 5G 영향 아래 있는 영역 구하기

stations을 순환하며 5G 영역의 (시작, 끝)을 구하고 이를 벡터에 저장하자.

기지국이 x 좌표에 설치되어있을 때, 영역의 시작은 max(0, x-w) 이고 영역의 끝은 min(n, x+w)가 된다.

이때, 시작 좌표가 (이전 영역의 끝+1) 보다 작거나 같다면 이전 영역과 겹친다는 이야기 이므로 이전영역에 합쳐서 끝 영역에 대한 정보만 변경시켜준다. 만약 시작 좌표가 (이전 영역의 끝+1)보다 크다면 겹치지 않는다는 뜻이므로 새로운 {시작, 끝} 정보를 벡터에 추가한다.

stations은 오름차순으로 정려되어있었으므로, 중복을 제거한 {시작, 끝} 정보도 자동으로 정렬 된다.

 

2) 빈 영역에 설치할 기지국 개수 구하기

5G 영역의 (시작, 끝) 정보를 온전히 구했으므로, 빈 영역에 설치해야 할 기지국의 개수만 구해주면 된다.

빈 영역의 시작점이 p이고 다음 5G 영역의 시작점이 st 일 때, 설치해야 할 기지국 개수는 st-p를 2*w+1로 나누어 올림한 값이다.

a를 b로 나누어 올림한 값은 (a+b-1)/b로 구할 수 있으므로, (st-p+2*w+1-1)/(2*w+1) = (st-p+2*w)/(2*w+1) 이 해당 빈 영역에 필요한 기지국 개수가 된다.

빈 영역의 기지국 개수를 구하고 p를 (5G 영역의 끝+1) 지점으로 보내 빈 영역을 반복적으로 탐색하자.

 

마지막 구역까지 기지국 개수를 구한 후 모두 더하여 리턴하면 정답이다.

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int solution(int n, vector<int> stations, int w) {

    vector<ii> v;

    for (auto x : stations) {
        int st = max(0, x-w);
        int en = min(n, x+w);
        int sz = (int)v.size();
        if (!sz || st > v[sz-1].Y+1) v.push_back({st, en});
        else v[sz-1].Y = max(v[sz-1].Y, en); //(st,en)가 가장 마지막 영역과 겹치면 끝 부분만 수정
    }

    int p = 1, cnt = 0;
    for (auto [st, en] : v) {
        cnt += (st-p+2*w)/(2*w+1); //(st-p)를 (2*w+1)로 나눈 후 올림한 값
        p = en+1;
    }

    if (p >= n+1) return cnt;
    return cnt += (n+1-p+2*w)/(2*w+1);
}