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

문제

문제풀이

배열을 새로 만들어서 거기에 기지국의 전파가 전달되는 인덱스의 번호를 모조리 저장하고 그것을 하나하나 확인하는 방식으로 짰다. 그랬더니 효율성 테스트에서 틀려버렸다... 아무래도 반복문이 너무 많아서 그랬던 듯 하다.

해당코드

function solution(n, stations, w) {
    var answer = 0;

    let start = 1;
    
    let arr =[]; //전파가 터지는 인덱스를 저장하는 배열
    let j=0;
    
  //전파터지는 인덱스를 저장하는 반복문
    for(let i=0;i<stations.length;i++){
        
        if(stations[i]-w < 0){
            j=0;
        }
        else j=stations[i]-w;
        
        
        while(j <= n && j <= stations[i]+w){
            arr.push(j);
            j++;
        }
        
    }
    
  //반복문으로 시작점부터 보면서 해당 좌표가 배열내에 없으면 기지국을 설치해주고 시작점을 옮겨주는 것으로 했다.
    while(start <= n){
        if(!arr.includes(start)){
            answer++;
            start+=2*w;
        }
        
        start++;
    }
    

    return answer;
}

머리를 써라 꼬린이씨!!!! 그래서 방법을 바꿔야했다.

참고블로그

기지국이 설치되어있는 범위내에 들어오게 되면 전파가 통하는 배열의 끝으로 시작점을 변경해주면 되는 것이었다! 그리고 아닐경우라면 기지국을 설치해주고 시작점을 변경해주면 된다.

그리고 굳이 배열을 따로 만들어서 저장해 줄 필요가 없다는 것을 알았다.. 끌끌..

function solution(n, stations, w) {
    var answer = 0;
    let start = 1;
    let index =0;
    
    while(start <=n){
        
        //범위 내에 있을 경우 시작점 위치 변경
        if(start >= stations[index] - w && start <= stations[index] + w){
            start = stations[index] + w;
            index++;
        }
        else{
            answer++;
            start+=2*w;
        }
        start++;
    }
    

    return answer;
}

머리를 써라...머리를 써라...머리..?머리..?