프로그래머스 - 기지국 설치 (Lv.3)

문제 링크

• 기지국 설치

구현(All Pass)

#include <iostream>
#include <vector>
using namespace std;

int solution(int n, vector<int> stations, int w)
{
    int answer = 0;
    
    // 전파가 도달되지 않는 부분 영역의 길이를 담는다.
    vector<int> not_comm_area;
    int comm_area = 2*w+1; // 기지국이 전파할 수 있는 영역의 길이
    int apt_idx, start = 1, end;
    int len;
    for(int i=0; i<stations.size(); i++){
        apt_idx = stations[i];
        end = apt_idx - w; // 전파가 전달되지 않는 마지막 아파트 다음을 가리킴
        len = end - start;
        if(len>=1)
            not_comm_area.push_back(len);
        start = apt_idx + w + 1; // 전파가 전달되지 않는 아파트 시작점
    }
    end = n+1;
    len = end - start;
    if(len>=1) not_comm_area.push_back(len);
    
    for(int i=0; i<not_comm_area.size(); i++){
        int cnt = not_comm_area[i]/comm_area;
        int r = not_comm_area[i]%comm_area;
        if(r>0) cnt++;
        answer += cnt;
    }
    
    return answer;
}

• 입력되는 데이터가 매우 크기 때문에 시간 복잡도를 무조건 O(n)으로 줄여야 한다고 생각했다.
• 땅따먹기라고 생각을 하면 좋다. 4G 기지국의 위치를 알고 있으므로 이를 5G 기지국으로 변경했을 때 차지하는 영역의 길이는 2 x W + 1 이다.
• 이제 전파가 전달되지 않는 영역의 길이를 계산하면 된다. 기지국을 중심으로 왼쪽으로 형성되는 전파 미전달 영역의 길이를 계산하고, 모든 기지국에 대한 탐색이 끝났다면, 마지막 기지국을 기준으로 오른쪽에 위치한 전파 미전달 영역의 길이를 계산해야 한다.
• 각 부분 영역에 대해서 설치해야 하는 기지국 개수를 계산하면 최소 기지국 개수를 구할 수 있다.