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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

해당 문제에서는 설치할 기지국의 개수가 중요하다. 어느 지점에 설치하는지는 몰라도 되기 때문에 개수만 구하는 방법으로 해결했다.

이미 설치된 기지국은 크게 3종류로 나눌 수 있다.

1. 첫번째 기지국
2. 마지막 기지국
3. 나머지 기지국
   이렇게 3종류로 나눈 이유는 각 기지국 사이에 새로운 기지국을 설치해야하는데, 첫번째 기지국과 마지막 기지국의 전파 도달 거리가 아파트를 벗어날 수 있기 때문이다. 따라서 각각의 케이스를 나눠주었다.

그렇다면 이제 각 기지국 사이에 몇 개의 기지국을 지을 수 있는지에 대해 알아보자. a 기지국과 b 기지국에 설치할 기지국의 개수를 구한다고 생각해보자. 두 기지국 사이에 전파가 도달하지 않는 범위는 a + w + 1 ~ b - w - 1 이 된다. 그리고 기지국 하나를 설치하면 2 x w + 1 의 전파 범위를 갖는다. 따라서 기지국 사이에 2 x w + 1가 몇 번 들어갈 수 있는지 계산해주면 쉽게 계산할 수 있다.

코드

C++

#include <vector>
using namespace std;

int countStation(int left, int right, int w) {
    int length = right - left + 1;
    int range = 2 * w + 1;
    int count = 0;
    while (count * range < length) count++;
    return count;
}

int solution(int n, vector<int> stations, int w) {
    int answer = 0;
    if (stations[0] - w > 1) answer += countStation(1, stations[0] - w - 1, w);
    for (int i = 1; i < stations.size(); i++)
        answer += countStation(stations[i - 1] + w + 1, stations[i] - w - 1, w);
    int last = stations.size() - 1;
    if (stations[last] + w < n) answer += countStation(stations[last] + w + 1, n, w);
    return answer;
}

Java

class Solution {
    public int countStation(int left, int right, int w) {
        int length = right - left + 1;
        int range = 2 * w + 1;
        int count = 0;
        while (count * range < length) count++;
        return count;
    }

    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        if (stations[0] - w > 1) answer += countStation(1, stations[0] - w - 1, w);
        for (int i = 1; i < stations.length; i++)
            answer += countStation(stations[i - 1] + w + 1, stations[i] - w - 1, w);
        int last = stations.length - 1;
        if (stations[last] + w < n) answer += countStation(stations[last] + w + 1, n, w);
        return answer;
    }
}