프로그래머스 Level 3 기지국설치

기지국설치 (프로그래머스 Level 3)

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

그동안 Level 2만 주구장창 풀다가 다시 AI가 추천해준 Level 3를 풀어보았다
AI가 ‘탐색’이라 추천해준 문제였지만 사실 ‘구현’에 가까운 듯한 문제였다

개인적으로 풀 때, 중점을 둔 부분은
‘전파가 닿지 않는 영역의 개수’였다
굳이 직접 임의의 위치에 기지국을 설치하는 것보다
그냥 필요한 영역의 개수만 있다면 얼마만큼 설치할지 구할 수 있다고 생각했다
(해당 부분의 설치 개수 = 전파가 닿지 않는 해당 영역 개수 / (기지국 전파 범위 * 2 + 1))
(다만 똑바로 나뉘지 않는 경우는 + 1)

처음에는 bool 배열을 통해 일일이 돌면서 true/ false 를 통해 구해주었으나
입력 데이터량이 굉장히 많았기에 stations를 도는 쪽으로 바꿔주었다
stations의 해당 설치 위치를 기준으로 ‘전파가 닿지 않는 개수’를 구할 수 있으므로
제한 시간 내에 문제를 풀 수 있었다

Code

#include <vector>

using namespace std;

int solution(int n, vector<int> stations, int w)
{
	int answer = 0;
	int tempPos = 0;

	for (int s : stations)
    {
        s--;
        int tempL = s - w - tempPos;
        tempPos = s + w + 1;

        if (tempL > 0)
        {
            int wide = (w * 2 + 1);
            int v = tempL / wide;
            if (tempL % wide != 0)
                v++;

            answer += v;
        }
    }

    if (tempPos <= n)
    {
        int tempL = n - tempPos;

        if (tempL > 0)
        {
            int wide = (w * 2 + 1);
            int v = tempL / wide;
            if (tempL % wide != 0)
                v++;

            answer += v;
        }
    }

	return answer;
}