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

 이 문제는 프로그래머스 level 3 문제이다. 이 문제는 입력이 2억이므로 O(n)으로도 약 2초가 걸린다. 따라서 배열을 사용한 방식으로는 불가능하다. now를 1로 하고, 입력으로 주어진 stations 를 활용해서 문제를 풀어야 한다. 이 생각을 하지 못하면 풀기 힘들 것 같다.

 

 

 

 

#include <iostream>
#include <vector>

using namespace std;

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

    return answer;
}