[레벨3] 기지국 설치

문제 링크

 

 

첫번째 풀이 (실패)

1. set에 1부터 n까지 아파트를 정리한다
2. stations를 순회하면 영향을 받는 아파트들을 set에서 지운다
3. set을 배열로 변환하여 순회하면서 연속적인 숫자가 아닌 부분 (즉 2번에서 지운 구간에 의해 나눠진 구간들)을 만날떄마다 range의 갯수로 나눠 기지국 갯수를 구한다.

function solution(n, stations, w) {
    var answer = 0;
    const numArr = Array.from({length: n},(_, i) => i+1);
    const set = new Set(numArr);
    for (const station of stations) {
        set.delete(station);
        for(let i = 1; i <= w; i++) {
            set.delete(station+i);
            set.delete(station-i);
        }
    }
    const arr = [...set];
    let left = 0;
    const range = w *2+1;
    
    for (let i = left; i < arr.length; i++) {
        while(arr[i+1] - arr[i] !== 1) {
            const count = i-left+1;
            answer += Math.ceil(count / range);
            left = i+1;
            break;
        }
    }
    return answer;
}

 

 

하지만 아파트 갯수는 2억 이하 자연수이므로 for O(n)은 효율성 테스트를 실패했다.

 

 

---

두번째 풀이 (성공)

문제의 핵심은
- 아파트 갯수는 2억 이하 자연수이므로 O(logN)이나 O(1) 이여야 한다
- station은 오름차순이다

 

1. stations을 순회하며 각 station 전후로 무영향 아파트의  갯수를 구한다
2. 무영향 아파트의 갯수를 사용하여 기지국 갯수를 구한다 Math.ceil(아파트갯수 / 전달범위갯수)
3. 전달 범위 갯수는 2w+1이다 (w+1+w)
4. stations 순회가 끝난 뒤 남은 아파트가 있으면 2번 계산식으로 기지국 갯수를 구해 더한다.

 

찾은 반례

stations순회 끝내고 마지막 하나만 남았을 떄

13 [3, 7, 11] 1  답: 4

function solution(n, stations, w) {
    var answer = 0;
    let curr = 1; // 현재위치
    const rangeWidth = 2*w+1; // 전달범위길이 = w개 + 중심1개 + w개
    let affectedRange; // [영향을 받는 범위의 시작, 끝]
    
    // station전후로 영향이 없는 구역의 갯수를 구한 뒤 필요한 기지국 갯수를 더한다.
    for (const station of stations) {
        if (station === 1){
            affectedRange = [1, 1+w]; // 기지국이 첫 말단일 때 범위
        } else if (station === n) { 
            affectedRange = [n-w, n]; // 끝 말단일때의 범위
        } else {
            affectedRange = [station-w, station+w]; // 그 외 범위 만약 최쇠최대를 넘어가면 [Math.max(station-w, 1), Math.min(station+w, n)]
        }
        const count = affectedRange[0] - curr; // 영향이 없는 구간의 아파트 갯수
        answer += Math.ceil(count / rangeWidth); // 구간 안에 필요한 최소 기지국 갯수 추가
        curr = affectedRange[1]+1; // 다음 무영향 구간 시작점
    }
    // station을 다 통과한 뒤 남은 아파트가 있을시
    if (curr <= n) {
        const count = n - curr+1; // +1!!! 남은 아파트 갯수
        answer += Math.ceil(count /rangeWidth);
        curr = n+1;
    } 
    return answer;
}