기지국 설치하기

문제 내용

이번 문제는 프로그래머스에 있는 문제이다. 링크

문제를 요약하자면 함수의 파라미터로 다음 3가지가 주어진다. 아파트 갯수, 기지국이 설치된 아파트의 위치 배열, 기지국의 전파거리 그리고 아파트는 1의 간격으로 일렬로 있다. 이때, 최소 몇개의 아파트에 기지국을 더 설치해야 모든 아파트에 전파가 닿는지가 문제이다.

풀이방법

위 문제는 그리디 알고리즘을 활용한 문제이다.

그리디 알고리즘은 각 단계에서 최적이라고 생각되는 것을 선택해서 최적의값을 구하는 값이다. 상황에 따라서 항상 최적을 보장하지 않는다. 각 단계에서 최적을 선택하는 것이 최종적으로 최적을 보장하거나 이러한 과정이 필요한 경우에 사용하는 것이 옳다.

기지국의 갯수를 계산하기 위해서는 거리를 활용해서 단순하게 덧셈, 뺄쎔, 나누기를 해서 몇개의 기지국을 더 설치해야 되는지 구한다고 생각하면 된다. 이를 효율적으로 진행하기 위해 기지국이 설치된 아파트 위치 배열을, 정렬해서 맨앞의 아파트와 가까운 곳부터 계산을 한다.

첫번째 아파트와 첫번째 기지국이 있는 아파트 사이에 몇개의 기지국을 설치해야 하는지 계산을 해본다. 그리고 그다음 제일 가까운 전파가 닿지 않는 아파트 와 그다음 기지국이 있는 아파트 사이에 몇개의 기지국을 설치해야 하는지 계산을 한다. 이 과정을 기지국이 있는 아파트들에 대해서 모두 반복한다.

그리고 마지막에 기지국을 설치한 아파트의 전파거리 바깥에 아직 아파트가 남아있는지 확인하고 있다면 몇개의 기지국을 더 설치해야 하는지 계산한다.

풀이

function solution(N, based, range) {
    let answer = 0;

    based.sort((a, b) => a - b);

    let start = 0;
    based.forEach((place, index) => {
        if (start < place - range) {
            const diff = place - range - start;
            answer += Math.ceil(diff / (range * 2 + 1));
        }
        start = place + range + 1;
    })

    if (start <= N) {
        const diff = N - start + 1;
        answer += Math.ceil(diff / (range * 2 + 1));
    }

    return answer;
}