[프로그래머스] Lv2. 주차 요금 계산 - JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 2

출처 : 프로그래머스 - 기지국 설치

문제

제한사항

📌 내가 생각한 풀이

N: 200,000,000 이하의 자연수이므로, 객체를 이용하여, 풀면 범위를 초과하여 런타임에러가 뜰것이다. 따라서 다른 방법으로 풀어야한다. 기지국이 설치되지 않은 구간의 개수를 구한 다음, (기지국의 전파범위*2)+1로 나누어주면 기지국설치 개수의 최소가 나온다. 이를 이용하여 구하자.

function solution(n, stations, w) {
    var answer = 0;
    let stack = [];
    let divider = (w*2)+1;
    let i = 0;
    stations.map((data,idx)=>{
        //start가 0 이하일 경우에는 0으로 맞춘다.
        let start = data-w;
        //finish가 n 이상일때는 n으로 맞춘다.
        let finish = data+w;
        if(start <=1){
            start = 1;
        }
        if(finish >=n){
            finish = n;
        }
        //스택에 start와 finish를 넣어준다.
        stack.push(start);
        stack.push(finish);
    })
    
    while(i !== stack.length){
        let num = 0;
        if(i ===0){
            if(stack[i] !== 0){
                num = stack[i]-1;
                answer += Math.ceil(num/divider);
                i++;
            }else{
                i++;
            }
        }else if(i === stack.length-1){
            if(stack[i] !== n){
                num = n-stack[i];
                answer += Math.ceil(num/divider);
                i++;
            }else{
                i++;
            }
        }else{
            num = stack[i+1] - stack[i]-1;
            answer += Math.ceil(num/divider);
            i+=2;
        }
    }
    return answer;
}

📌 느낀점

처음 문제를 접했을 땐, 바로 객체로 풀면 되겠구나 생각했는데 주어진 N의 범위가 매우 커서, 시간복잡도 뿐만아니라 런타임 에러가 뜬다. 이를 해결하기 위해서 갯수를 구한다음 나누는 방법을 생각했다. 문제를 풀때 주어진 수의 범위를 꼭 보고 풀어야 정답에 근접할 수 있음을 알게되었다.