[프로그래머스] 단속카메라

문제

단속카메라

https://school.programmers.co.kr/learn/courses/30/lessons/42884

 

 

예시 코드

function solution(routes) {
  routes.sort((a, b) => a[0] - b[0]);

  let camCnt = 0;
  let lastCamPos = -Infinity;

  for (const [start, end] of routes) {
    if (start > lastCamPos) {
      camCnt++;
      lastCamPos = end;
    } else lastCamPos = Math.min(lastCamPos, end);
  }

  return camCnt;
}

 

풀이

모든 차량을 커버할 수 있는, 최소한의 단속 카메라 개수를 구하는 문제입니다.

routes를 진입 지점(start)을 기준으로 정렬해 차량 경로를 순차적으로 확인할 수 있게 합니다.

가능한 경우, 마지막 카메라 위치를 현재 차량의 진출 지점으로 갱신합니다.

 

routes를 순회하며 두 가지 경우로 나누어 처리합니다.

1. 차량 경로가 겹치지 않는 경우
   진입 지점이 마지막 카메라 위치보다 나중에 위치한 경우입니다.
   카메라 개수를 늘리고, 마지막 카메라 위치를 진출 지점으로 갱신합니다.
2. 차량 경로가 겹치는 경우
   진입 지점이 마지막 카메라 위치보다 먼저 위치한 경우입니다.
   마지막 카메라 위치를 진출 지점과 비교하여 더 앞의 위치로 갱신합니다.