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

https://school.programmers.co.kr/learn/courses/30/lessons/12979

프로그래머스

 

처음에는 이분탐색을 의심했다. 새로 설치할 기지국의 개수를 정해놓고 체크하는 방식의 문제가 백준에 존재하기 때문이다. 그렇게도 할 수는 있지만 이 문제의 n은 무려 2억으로 반드시 O(N) 이하로 처리해야 정답이다.

 

 

이 문제의 핵심은 저 회색칸을 배열로 만드는 것이다. 그리고 그 회색칸을 주어진 기지국이 커버할 수 있는 값을 계산하면 된다. 2 * w + 1 이 하나의 기지국이 커버할 수 있는 범위이기 때문이다.

 

이 방법을 사용하면 Station의 칸 수 만큼의 계산을 요구하기 때문에 O(10000)으로 모든 케이스를 해결 할 수 있다.

 

저 회색 칸을 배열로 만드는 것이 살짝 어렵고 아이디어를 도출하는 것도 쉬운것은 아니었다. 이전에 풀던 흔적이 있던 문제였는데 문제를 잡고서 바로 풀 수 있었다. 조금은 성장한 것 같아 기분이 좋다.

 

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

int solution(int n, vector<int> stations, int w)
{
    int answer = 0;
    int tmp = 1;
    int left, right;
    
    vector<int> voidSite;
    for(int i = 0; i < stations.size(); i++){
        int station = stations[i];
        left = station - w;
        right = station + w;
        
        if(left - tmp > 0){
            voidSite.push_back(left - tmp);
            tmp = right + 1;
            
        }else{
            tmp = right + 1;
        }
    }
    
    if(right < n){
        voidSite.push_back(n - right);
    }
    
    int value = 2 * w + 1;
    for(int i : voidSite) {
        answer += i / value;
        
        if(i % value != 0) answer++;
    }    
    return answer;
}