C++ / 프로그래머스 / 기지국 설치

문제

 

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

프로그래머스

 

문제풀이

 

모든 아파트에 전파를 전달하기 위해, 이미 설치된 기지국을 제외하고 최소 몇 개를 설치해야 되는지 구하는 문제이다.

제한사항을 보면 기지국의 위치를 알려주는 벡터인 stations는 오름차순으로 정렬되어 있다고 되어있다.

따라서 정렬할 필요 없이 1부터 n까지 돌면서 기지국을 설치하면 된다.

 

1부터 탐색하면서 이미 설치된 기지국 전파에 닿는지를 확인한다.

닿지 않는다면 효율적인 설치를 위해 1이 전파의 왼쪽 끝에 닿게 해야 한다.

1 + 전파 도달 거리(W)에 기지국을 설치하면 1~1+w*2까지 전파가 닿는다.

 

만약 이미 설치된 전파에 닿는다면 idx를 전파의 오른쪽 끝인 stations[idx2] + w로 옮기고 반복문을 돌리면 된다.

 

코드

#include <vector>
using namespace std;

int solution(int n, vector<int> stations, int w)
{
    int answer(0), idx(0), idx2(0);

    for (idx = 1; idx <= n; ++idx) {
        if (idx2 < stations.size() && stations[idx2] - w <= idx && idx <= stations[idx2] + w) {
            idx = stations[idx2] + w;
            ++idx2;
        }
        else {
            idx += (w * 2);
            answer++;
        }
    }


    return answer;
}