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

adultlee·2023년 6월 8일
0
post-custom-banner

문제 링크

프로그래머스 문제

풀이

문제를 보자마자 든 풀이 방식은 그리디를 이용한 방식이다.
첫번째 station을 입력받은 이후, 그 직후 이전까지의 상황에 대해서만 올바른 결정을 했다면, 그 이후부터는 그 결정에 대해서는 더이상 신경쓰지 않아도 되기 때문이다.

따라서 두가지 중요한 점을 생각할 수 있었다.

  1. station의 입력 특수한 위치를 고려(맨 앞이거나, 맨 뒤)
  2. 빈공간의 길이를 알아 낼수 있다면, 정확한 위치는 중요하지 않다. -> 왜냐하면 그 공간에 들어갈 수 있는 최소의 station값은 정해져있기 때문이다.

Math.ceil() 함수는 올림 함수이다.

코드

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

    stations.map( (station,index) => {
       if(startIndex < station - w){
           answer+= Math.ceil( (station -w -startIndex) / (w+w+1 ))
       }
       startIndex = station + w +1;
       if(index === stations.length-1 && startIndex <= n){
           answer+= Math.ceil( (n -startIndex +1) / (w+w+1))
       }
   })

    return answer;
}
post-custom-banner

0개의 댓글