프로그래머스 기지국 설치

문제 풀러 GO

코딩테스트 연습 - 기지국 설치

 

이번에 푼 문제는 기지국 설치입니다. 이번에는 javascript를 이용하여 문제를 풀었습니다.

이 문제를 바로 풀 수는 없었습니다. 그래서 해설을 보면서 풀었고, 풀면서 이해가 되지 않았던 부분과 그 부분을 해결하는 과정을 기록으로 남깁니다!

 

문제 해결

---

function solution(n, stations, w) {
    var answer = 0;
    var stationsIdx = 0;
    var i = 1;
    while(i <= n){
        if(stations.length > stationsIdx && 
           stations[stationsIdx]-w <= i+w*2 && stations[stationsIdx]+w >= i+w*2){
            //갈 곳이 범위 안
            i = stations[stationsIdx]+w+1;
            stationsIdx++;
        }else{
            //범위 밖
            i+=w*2+1;
        }
        answer++;
        
    }
    
    return answer;
}

 

저의 처음 코드입니다.(정답 X)

• 기지국을 설치했을때의 맨 끝의 위치가 전파 범위 안이라면 그 범위를 지나가도록 했습니다.
• 만약 전파 범위 안이 아니라면 기지국 설치시의 전파 범위의 끝 위치의 다음칸으로 가도록 했습니다.

그런데 이 코드에 문제가 있었습니다.

테스트 케이스는 맞았지만 제출을 하니 거의 20점이었습니다.

 

위와 같은 테스트 케이스는 통과하지 못하기 때문이었던 것 같습니다.

처음 구간에 기지국이 설치되어있을 경우를 처리할 수 없었기 때문입니다.

저는 그래서 위와 같은 코드를 통과하기 위해 

if(stations.length > stationsIdx && i===stations[stationsIdx]){
    i = stations[stationsIdx]+w+1;
    stationsIdx++;
    continue;
}

이런 코드를 while문의 맨 처음 부분에 작성하였습니다.

그런데 역시 정답은 아니었습니다.

세모는 기지국(전파범위(w)는 2인 기지국)

제 코드의 문제는 이 그림을 보면 알 수 있습니다.

while문에 코드를 추가하였지만 그 코드는 기지국이 설치된 곳만 처리할 수 있었습니다.

처음 구간이 전파범위일 경우는 처리하지 못했던 것입니다.

 

그래서 위와 같은 테스트 케이스를 추가했을 경우 통과하지 못했죠.

범위를 확인해야 한다는 것을 알았고 그래서 위에서 추가한 코드를 아래와 같이 수정했습니다.

if(stations.length > stationsIdx && 
   stations[stationsIdx]-w <= i && stations[stationsIdx]+w >= i){
    i = stations[stationsIdx]+w+1;
    stationsIdx++;
    continue;
}

 이렇게 수정하니 효율성 테스트 빼고 모두 통과되었습니다.

function solution(n, stations, w) {
    var answer = 0;
    var stationsIdx = 0;
    var i = 1;
    while(i <= n){
        if(stations.length > stationsIdx && 
           stations[stationsIdx]-w <= i && stations[stationsIdx]+w >= i){
            i = stations[stationsIdx]+w+1;
            stationsIdx++;
            continue;
        }
        if(stations.length > stationsIdx && 
           stations[stationsIdx]-w <= i+w*2 && stations[stationsIdx]+w >= i+w*2){
            //갈 곳이 범위 안
            i = stations[stationsIdx]+w+1;
            stationsIdx++;
        }else{
            //범위 밖
            i+=w*2+1;
        }
        answer++;
        
    }
    
    return answer;
}

전체 코드는 이렇게 수정이 되었고 while문의 맨 처음 if문과 2번째 if문에서 같은 코드를 실행시키고 있습니다.

두번째 if문에서는 기지국도 설치하고 원래 전파 범위이던 곳을 지나가는 코드인데 else문에서 기지국을 설치하고, 첫 번째 if문에서 원래 전파 범위를 넘어가도록 하는 것이 더 나을 것 같아 if문을 한개로 만들어줬습니다.

 

function solution(n, stations, w) {
    let answer = 0;
    let stationsIdx = 0;
    let i = 1;
    while(i <= n){
        if(stationsIdx < stations.length &&
            stations[stationsIdx]-w <= i && stations[stationsIdx]+w >= i){
            i = stations[stationsIdx]+w+1;
            stationsIdx++;
        }else{
            i+=(w*2+1);
            answer++;
        }
    }

    return answer;
}

이렇게 해서 통과를 했습니다. 같은 코드에서 변수 선언을 let 대신 var로 했을때는 통과를 하지 못했습니다.

그 이유는 잘 모르겠지만 일단 var와 let에 대해 더 알아봐야겠습니다!