프로그래머스 - 기지국 설치

프로그래머스 - 기지국 설치

n의 범위가 200,000,000 이하의 자연수이기 때문에 n을 이용해서 풀면 시간초과가 난다. (벡터 할당만해도 시간초과가 난다)
따라서 stations 벡터를 이용해서 풀어야 하는데, 그리디하게 기지국을 설치해나가면서 풀어도 된다.

기지국 설치 위치를 pivot이라고 하고, 첫 pivot 값을 1 + w로 설정한다(pivot은 pivot - w ~ pivot + w까지를 커버). 그 후 idx가 stations의 크기보다 작을 때 까지 stations[idx]와 pivot을 비교를 한다.
1. 만약 stations[idx]보다 pivot이 작다면, 기지국이 필요하다는 것을 의미하기 때문에 기지국을 설치한다. 그 후 pivot 값을 현재 pivot의 오른쪽 범위와 다음 pivot의 왼쪽 범위가 겹치지 않도록 pivot에 w * 2 + 1만큼을 더해서 업데이트 해준다.
2. 만약 pivot의 stations[idx]보다 크다면, 이미 설치된 기지국이 커버하는 범위에 pivot이 포함되어 있다는 것을 의미하고, 추가적인 기지국을 설치할 필요없다는 것이다. 따라서 idx를 증가시켜주고, pivot을 위와 같은 방식으로 업데이트 해준다.

위 과정을 마치고 나와도 pivot이 커버하는 범위가 아직 n까지 도달하지 못했을 수 있다.
N = 5, stations = [2], w = 2 // Answer = 1의 경우 기지국을 1개도 설치하지 않고, pivot은 7이 되고 위 과정이 끝난다. 그러나 아직 5번 위치는 기지국이 커버하지 못한다.
따라서 정답을 반환하기 전에 pivot - w가 n보다 큰지를 확인해줘야한다.

코드는 아래와 같다.

#include <iostream>
#include <vector>

using namespace std;

int solution(int n, vector<int> stations, int w)
{
    int answer = 0;
    int s = stations.size();
    int pivot = 1 + w;
    int idx = 0;
    while(idx < s) {
        if(pivot < stations[idx]) {
            pivot = pivot + w * 2 + 1;
            answer++;
        } else {
            pivot = stations[idx] + w * 2 + 1;
            idx++;
        }
    }
    
    while(pivot - w <= n) {
        answer++;
        pivot = pivot + w * 2 + 1;
    }
    
    return answer;
}