[Javascript/PGS] Lv.3 : 기지국 설치

 

https://school.programmers.co.kr/learn/courses/30/lessons/12979?language=javascript#

프로그래머스

---

 

프로그래머스 레벨 3 문제.

예전에 c++로 풀다가 해결 못했던 문제인데, 오늘 js로는 해결했다

그래도 사고력이 좀 늘었나..^^ 약간 성장한 듯

 

특별한 알고리즘을 쓰는 문제는 아니지만, 신경써야 할 부분이 은근히 많다.

 

메인 힌트는 n의 범위이다. (매우 크기 때문에 stations를 활용해야 한다)

주의할 점은 중간에 빈 구간 구할 시, 음수나 0이 나오는 경우를 예외처리해줘야 한다는 것!!!

 

근데 제출하니까 정확도 100% 나오는데 효율성에서 시간 초과가 하나 떴다.

이거 왜 이러나 싶어서 질문 게시판을 뒤져보니,

Java로 풀이한 사람들이 반올림 연산(Math.ceil) 때문에 오열했던(...)흔적이 있었다.

 

아니 왜요?

 

반올림 함수가 은근 효율이 좋지 않다고 한다.

이걸 보고, js도 반올림 연산 쓰면 초과되겠네 싶어서 기존 코드의 Math.floor 함수를 모두 직접 연산으로 바꿔주었다.

그랬더니 바로 통과~~ㅎㅅㅎ

 

나의 풀이

function solution(n, stations, w) {
    let answer = 0;
    let currentNum = 1;
    let noSignal = 0;
    let width = 2*w+1;
    // n 범위가 크니까 stations으로 연산해야겠다고 판단
    for(let i=0; i<stations.length; ++i){
        noSignal = stations[i]-w-currentNum;
        if(n==5) console.log(noSignal, currentNum)
        currentNum = stations[i]+w+1;
        if(noSignal<=0) continue; // 주의
        answer += (noSignal-noSignal%width)/width;
        if(noSignal%width > 0) answer += 1;
    }
    if(n > stations[stations.length-1]+w){
        noSignal = n-(stations[stations.length-1]+w);
        answer += (noSignal-noSignal%width)/width;
        if(noSignal%width > 0) answer += 1;
    }
    return answer;
}