[JS/Programmers] 12979. 기지국 설치

💬 문제

문제 난이도: Programmers Lv.3

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12979

❗️접근방법

구현 + 효율성

👆 1차 코드 (정확성 ✅, 효율성 ❌)

function solution(n, stations, w) {
    const onService = new Array(n).fill(0); // --- 1️⃣
    for (let i = 0 ; i < stations.length; i+=1){ // --- 2️⃣
        const station = stations[i] -1;
        for (let j = Math.max(0, station - w); j <= Math.min(station + w, n-1); j+=1){
            onService[j] = 1;
        }
    }
    // console.log(onService)
    let idx = onService.findIndex(elem=>elem===0); // --- 3️⃣
    let answer = 0;
    while (idx !== -1 && idx < n){ // --- 4️⃣
        answer += 1;
        let i;
        for (i = idx; i <= Math.min(n-1, idx + 2*w); i+=1){
            onService[i] = 1; 
        }
        idx = onService.findIndex(elem=>elem===0);
        // console.log(onService)
    }
    return answer;
}

구현 방법
1️⃣ onService 배열은 전파가 도달하는지 여부를 나타낸다.
2️⃣ 이중 for문을 돌며 이미 전파가 도달하는 곳을 1로 초기화한다.
3️⃣ idx는 아직 전파가 도달하지 않은 위치 중 가장 작은 값이다.
4️⃣ 아직 전파가 도달하지 않은 위치가 남아 있을 때까지 onService 배열을 순회하며 설치해야 할 기지국 수를 늘려준다.

시간초과 원인
stations 배열의 크기와 같은 onService 배열을 만들어
모든 원소에 접근해 1로 초기화하는 과정에서 시간이 오래 소요됨. (이중 for문을 거쳐야 하니까)
그리고 아직 전파가 도달하지 않은 위치를 찾기 위해 while 문 안에서 findIndex를 하는 과정에서도 O(n^2) 시간이 걸림.

✌️ 2차 코드 (통과 🎉)

function solution(n, stations, w) {
    let answer = 0;
    let station = stations.shift(); // --- 1️⃣
    let idx = 1; // --- 2️⃣
    while (idx <= n){ // --- 3️⃣
        if(idx < station - w){ // --- 4️⃣
            answer += Math.ceil((station-w-idx) / (2*w+1));
            idx = station + w + 1;
        }else{ // --- 5️⃣
            idx = station + w + 1;
        }
        if (stations.length <= 0) break;
        else station = stations.shift();
    }
    
    if (idx <= n){ // --- 6️⃣
        answer += Math.ceil((n - idx + 1)/ (2*w+1));
    }
    return answer;
}

구현 방법
모든 위치에 대해 전파 도달 여부를 확인하고 초기화할 필요 없다.(확인하면 시간 초과남)
1️⃣ stations 배열은 오름차순 정렬되어 있다.(문제 조건)
-> shift 메소드를 활용해 앞에서 원소를 pop 하고 변수 station이 이 원소를 가리킨다.
2️⃣ idx는 현재 위치를 가리킨다.
3️⃣ 전체 아파트를 끝까지 순회한다.
4️⃣ 현재 위치(idx)가 전파가 도달하지 않는 곳이라면
-> (제일 가까운 전파 도달 위치 - 현재 위치) / (기지국 하나당 전파 전달 범위) 의 올림
-> 제일 가까운 전파 도달 위치 - 현재 위치 : 전파 도달 안하는 아파트 개수
-> 몇 개의 기지국이 추가적으로 설치되어야 하는지 알 수 있음.
-> 현재 위치 변경 (5️⃣ 참고)
5️⃣ 현재 위치(idx)가 전파가 도달하는 곳이라면
-> station + w: station으로 인해 전파를 받는 가장 큰(멀리 있는) 위치
-> station + w + 1: 전파를 받는 곳인지 아닌지 아직 확인이 안된 가장 작은(현재 위치로부터 가장 가까운) 위치
6️⃣ 이미 설치된 기지국의 전파 전달 위치보다 큰(먼) 위치인데 전파가 안 오는 경우
-> (마지막 아파트 - 현재 위치 + 1) / (기지국 하나당 전파 전달 범위) 의 올림