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

프로그래머스 Level 3 - 단속카메라

• 문제 분류 : 탐욕법(Greedy)
• 문제 출처 : 프로그래머스 Level 3 - 단속카메라

📌 문제 설명

📌 생각한 풀이 방법

1. 차량이 나간 지점을 기준으로 배열을 정렬한다.
2. 현재 차량의 나간 지점보다 다음 차량의 진입 지점보다 작은 경우만 카메라를 하나 더 설치한다.
3. 모든 차량을 검사할 때까지 조건 2를 반복한다.

📌 풀이

function solution(routes) {
  let answer = 0;

  // 차량이 나간 지점을 기준으로 배열을 정렬한다

  let lessThanZero = routes
    .filter((item) => item[1] < 0)
    .sort((a, b) => Math.abs(b[1]) - Math.abs(a[1]));

  let biggerThanZero = routes
    .filter((item) => item[1] >= 0)
    .sort((a, b) => a[1] - b[1]);

  // 음수와 양수를 나눠서 정렬한 후, 정렬된 음수 배열 + 정렬된 양수 배열로 합친다
  let sortedRoutes = [...lessThanZero, ...biggerThanZero];

  while (sortedRoutes.length) {
    // 모든 차량을 검사할 때까지 반복한다
    let cameraLocation = sortedRoutes.shift()[1];
    while (sortedRoutes.length) {
      if (sortedRoutes[0][0] <= cameraLocation) {
        sortedRoutes.shift(); // 카메라를 더 설치할 필요 없는 경우
      } else {
        break; // 카메라를 하나 더 설치해야 하는 경우
      }
    }
    // 현재 차량의 나간 지점보다 다음 차량의 진입 지점보다 작은 경우만 카메라를 하나 더 설치한다.
    answer++;
  }

  return answer;
}