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

문제 출처

프로그래머스 lev3 - 기지국 설치

나의 풀이

1차시도 (53.7/100)

function solution(n, stations, w) {
  let once = 1 + (w*2)
  let edge = [0, 0]
  let stk = 0
  let answer = 0 

  for(let i=0; i<stations.length; i++){
    let ls = stations[i] - w 
    let rs = stations[i] + w

    if(ls <= 1) {
      stk += once - (1-ls)
      edge[0]++
    }
    if(rs >= n) {
      stk += once - (rs-n)
      edge[1]++
    }
    if(ls > 1 && rs < n) stk += once
  }

  if(edge[0] === 0){
    let el = (stations[0]-w) - 1
    
    while(el - once > 0) {
      answer++ 
      el -= once
      stk += once
    }

    if(el > 0 && el - once <= 0) {
      answer++ 
      stk += el 
    }
  }

  if(edge[1] === 0){
    let er = n - (stations[stations.length-1]+w)

    while(er - once > 0) {
      answer++ 
      er -= once
      stk += once
    }

    if(er > 0 && er - once <= 0) {
      answer++ 
      stk += er
    }
  }

  while(stk < n) {
    answer++
    stk += once 
  }
  
  return answer
}

다른 풀이 1

굳이 따지자면 결정 알고리즘 아이디어라고 이름 붙일 수 있는 유형
(시작지점 0부터 시작해서 else일 때와 if일 때 각각 해당하는 방식으로 시작지점을 업데이트해주는)
⇒ 크기가 커서 그리디/이분탐색 등으로 생각하려 했으나, 결정 알고리즘 아이디어로 풀어나갈 수 있다면 완전탐색도 시도해볼만 한 것 같다.

나는 먼저 주어진 stations을 배치해놓고 남은 공간들을 채워넣는 식으로 접근하려 했으나,,

아래 풀이에서는 미리 stations을 배치해놓는 게 아니라 아예 0부터 시작해서 하나 씩 전진해준다.

1씩 전진하다가 원래 배치되어야 하는 기지국을 만나면 start 지점을 그 기지국의 끝지점으로 이동시켜주고 해당 기지국 배열을 삭제해준다.
start = stations[0]+w, stations.shift();

원래 배치되어야 하는 기지국 범위가 아니라면 전파 범위 만큼 전진해주고 기지국 개수를 카운트해준다.
start += w*2, answer++;

function solution(n, stations, w) {
  let answer = 0;
  let start = 0;
  // index 혼동을 방지하기 위한 장치 
  stations = stations.map((v) => v - 1);

  while (start < n) {
    if (start >= stations[0] - w && start <= stations[0] + w) {
      start = stations[0] + w;
      stations.shift();
    } else {
      start += w * 2;
      answer++;
    }
    start++;
  }

  return answer;
}

다른 풀이 2

미리 배치된 기지국의 위치가 오름차순으로 배치되므로 왼쪽과 오른쪽의 범위를 쉽게 구할 수 있다.

const cal = (start, end, w) => {
  // 전파 안 되는 범위 
  let len = end - start + 1
  // 기지국 1개의 전파 범위 
  let range = (w*2)+1 

  // 기지국 개수 
  let cnt = 0 
  while(cnt*range < len){
    cnt++
  }
  return cnt 
}

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

  // 첫번째 기지국 왼쪽에 추가 설치 (왼쪽에 남는 공간이 있다면)
  if(stations[0]-w-1 >= 1){
    answer += cal(1, stations[0]-w-1, w)
  }

  // 기지국과 기지국 사이에 추가 설치 
  for(let i=1; i<stations.length; i++){
    answer += cal(stations[i-1]+w+1, stations[i]-w-1, w)
  }

  // 마지막 기지국 오른쪽에 추가 설치 ((오른쪽에 남는 공간이 있다면))
  if(stations[stations.length-1]+w+1 <= n){
    answer += cal(stations[stations.length-1]+w+1, n, w)
  }
  return answer
}

참고

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