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

프로그래머스 기지국 설치 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

n개의 아파트가 나열되어 있으며, 일부 아파트 옥상에는 기지국이 설치되어 있습니다.
기지국은 양쪽으로 w만큼의 전파를 보내줄 수 있습니다.
현재 설치된 기지국으로 모든 아파트에 전파를 전달하지 못할 수 있습니다.
모든 아파트에 전파를 전달하기 위해 증설해야 할 기지국 개수의 최솟값을 리턴해야 합니다.

문제 풀이

전달받지 못하는 아파트들을 찾아서 기지국을 설치하여 모든 아파트에 전파가 보내지도록 해야 합니다.

일단 기지국은양쪽으로 w만큼의 전파를 보내줄 수 있으니 w*2+1만큼의 전파 범위를 가집니다.

나열된 아파트들 중 전파를 받지 못하는 아파트 구간들이 존재합니다.
최대 2억개의 아파트가 존재하기에 배열 앞에서부터 찾아가기에는 시간초과가 나게 됩니다.
그러니 미리 설치된 기지국을 기준으로 오름차순으로 정렬 후 기지국과 기지국 사이의 빈 공간을 찾아 기지국을 설치해주면 됩니다.
처음에는 1번 아파트부터 시작하기에 시작을 1로 잡아준 후 다음으로 나오는 기지국을 기준으로 전파범위 중 왼쪽 맨 끝에 해당하는 위치를 계산해줍니다.
왼쪽 맨 끝의 해당하는 위치는 stations[i] - w - 1의 값이 됩니다.

이후 시작 위치와 끝 위치를 비교하여 만약 시작 위치가 더 뒤에 있다면 빈 아파트가 있다는 뜻이므로 끝 위치-시작 위치+1가 전파를 받지 못하는 아파트의 범위가 됩니다.
이제 범위를 가지고 들어갈 기지국의 수를 계산해주면 됩니다.

그리고 다음 계산의 시작 위치는 계산한 기지국의 오른쪽 맨 끝에 해당하는 위치로 설정해준 후 다음 기지국과 계산을 진행해주면 됩니다.

마지막의 기지국을 계산한 후 맨 뒤에 있는 아파트에게도 전파가 잘 전달되었는지도 확인해주어야 합니다.

전체 코드

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;

int solution(int n, vector<int> stations, int w){
    int answer = 0;
    int spreadSize = w * 2 + 1;
    
    //시작 지점
    int start = 1;
    for(int i = 0; i < stations.size(); i++)
    {
        //설치된 기지국의 맨 뒤의 전파 범위
        int end = stations[i] - w - 1;
        if(start <= end)    //설치된 기지국의 맨 뒤의 전파 범위보다 시작 지점이 뒤에 있을 경우 기지국 추가 설치
        {
            int len = end - start + 1;
            if(len <= spreadSize)
                answer += 1;
            else
            {
                answer += len / spreadSize;
                if(len % spreadSize != 0)
                {
                    answer += 1;
                }
            }
        }
        //설치된 기지국의 맨 앞의 전파 범위
        start = stations[i] + w + 1;
    }
    //마지막 기지국의 전파 범위가 마지막 아파트까지 전파가 닿는지 확인
    if(start <= n)
    {
        int len = n - start + 1;
            if(len <= spreadSize)
                answer += 1;
            else
            {
                answer += len / spreadSize;
                if(len % spreadSize != 0)
                {
                    answer += 1;
                }
            }
    }
    
    return answer;
}

출저

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