[CodeKata] 프로그래머스: 1.10(월), 기지국 설치

🥋 Oooth More!! (Level 3) 

 

🧮 풀이

function solution(n, stations, w) {
  let sects = stations.reduce((acc, cur) => [...acc, cur-w-2, cur+w], [])
  let start_block, end_block = false;
  const r = 2*w + 1;
  let answer = 0;
  
  if (sects[0] < 0) {
    sects.shift();
    start_block = true;
  }
  if (sects[sects.length-1] > n-1) {
    sects.pop();
    end_block = true;
  }
  
  if (!start_block) sects.unshift(0);
  if(!end_block) sects.push(n-1);
  
  while (sects.length) {
    const [s,e] = sects.splice(0,2);
    answer += Math.ceil((e-s+1)/r);
  }
  
  return answer
}

• sects는 데이터가 닿지 않는 아파트들의 시작과 끝점들을 저장하는 배열이다. 우선, w를 활용해 stations 각 좌표의 양 끝값을 reduce()로 넣어준다.
• start_block/end_block은 양 끝에 데이터가 닿는지 여부를 저장하는 변수다. 이후, 기본적으로 양 끝(0, n-1)을 시작점과 끝점으로 포함시킬 것이지만, 양 끝쪽에 데이터가 터진다면 추가하면 안되므로 이를 Boolean으로 관리한다.
• r은 데이터가 닿는 범위, answer는 정답을 누적할 변수이다.
• sects의 양 끝값이 (0 ~ n-1) 범위를 벗어났다면 양 쪽 끝에는 데이터가 닿는 것이다. 이 땐, 그 값을 빼주고 block을 true로 바꾼다.
• 다음으로, 양 쪽 각각이 block이 아닌 경우에는 끝값(0, n-1)을 넣어준다. 최종적으론, sects 요소가 2개쌍씩 데이터가 닿지 않는 시작과 끝 인덱스가 된 것이다.
• 이를, while 반복문을 통해 2개씩 빼오고(splice), 이 길이를 r로 나눈 몫을 Math.ceil해서 answer에 더해준다. (길이가 6이고 범위가 5라면, 최소 2개가 필요하므로!)

이 풀이는 정확성을 통과했지만, 효율성 테스트를 통과하지 못했다.

데이터가 닿는 영역여부를 true/false로 만든 배열을 탐색하는 방법부터, 효율성을 높이기 위해 다양한 시도를 했지만 풀지 못하였다.

역시 좀 더 고도화된 풀이가 적용되어야 통과할 수 있을 것 같다. 이를 모범답안으로 알아보겠다!

 

🖇 리뷰

function solution (n, stations, w) {
  let answer = 0;
  const coverage = w * 2 + 1;
  
  const endPoint = n - stations.reduce((prev, cur) => {
    const appartments = cur - w - 1 - prev;
    answer += appartments > 0 ? Math.ceil(appartments/coverage) : 0;
    return cur + w;
  }, 0);
  
  if(endPoint > 0)
    answer += Math.ceil(endPoint / coverage) + 1;
  
  return answer;
}

* 출처 : https://velog.io/@longroadhome/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LV.3-%EA%B8%B0%EC%A7%80%EA%B5%AD-%EC%84%A4%EC%B9%98%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LV.3-%EA%B8%B0%EC%A7%80%EA%B5%AD-%EC%84%A4%EC%B9%98-JS

 

• answer과 coverage(=r) 은 위에서 내가 정의한 변수와 같은 용도이다.
• endPoint는 n(끝)과 stations.reduce() 로 오른쪽 좌표를 갱신하면서 마지막 오른쪽 좌표와의 차이값을 저장한 변수다.
• 위 값이 음수(마지막 오른쪽 좌표가 끝보다 더 크다면) 오른쪽 끝엔 데이터가 닿는 것이며, 그렇지 않을 경우엔 남은 닿지 않는 구간을 계산해주는 것이다.
• reduce() 내, appartments는 이전좌표 끝점(0 or prev)와 현재좌표의 시작점(cur-w-1) 사이의 아파트 개수를 의미한다.
• 위가 존재한다면, Math.ceil(appartments/coverage) 만큼 answer에 더한다. => 모범답안은 Math.floor() + 1 등으로 복잡했지만, 간단하게 ceil()로 해결이 된다!
• 다음으로, 현재좌표의 끝점인 (cur+w) 를 다음 prev 값으로 최신화 시켜준다.
• endPoint 최종값이 0보다 크다면, 데이터가 닿지 않는 곳이 남아있다. 이 값 역시 Math.ceil() 처리로 anwer에 더해준다.

 

간단하게 생각하면, n이나 stations 별도의 가공 없이 reduce()를 통한 좌표 최신화로 풀 수 있는 생각보다 쉬운 문제였다..!