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

문제 출처

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

나의 풀이

다른 풀이

그리디 문제
(그리디에서는 정렬 개념이 유용한 것 같다)

더 빨리 진입한 순으로 계산하면 이후에 중복을 피할 수 있다.
차량 진입 시점(routes[i][0])을 기준으로 오름차순 정렬을 한다.
routes.sort((a, b) => a[0] - b[0])

1. 이전 차량 진출 시점(prevOut) < 현재 차량 진입 시점인 경우(currIn)
   ⇒ 카메라 추가 (answer++)
   ⇒ 진출 시점을 현재 차량의 진출 시점으로 갱신

2. 이전 차량 진출 시점(prevOut) > 현재 차량 진출 시점인 경우(currOut)
   ⇒ 진출 시점을 현재 차량의 진출 시점으로 갱신

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

  let prevOut = routes[0][1]
  let answer = 1

  
  for(let i = 1; i < routes.length; i++) {
    const [currIn, currOut] = routes[i]
    
    if(prevOut < currIn) {
      answer++
      prevOut = currOut
    }
    if(prevOut > currOut) {
      prevOut = currOut
    }
  }
  
  return answer;
}

다른 풀이 2

진출 시점으로 오름차순 정렬을 하고
카메라의 위치를 할당한다.

카메라의 위치보다 진입 시점이 뒤에 있을 경우
카메라를 그 진입 시점에 추가한다.

const solution = (routes) => {
  let answer = 0;
  routes.sort((a, b) => {
    return a[1] - b[1];
  });
  let camera = -30001;
  for (let i = 0; i < routes.length; i++) {
    if (camera < routes[i][0]) {
      answer++;
      camera = routes[i][1];
    }
  }
  return answer;
};

다른 풀이 3

function solution(routes) {
  var answer = [];
  routes.sort((a, b) => a[1] - b[1]);
  for (let item of routes) {
    if (!checkCam(item, answer)) {
      answer.push(item[1]);
    }
  }
  return answer.length;
}

function checkCam(route, cameras) {
  for (let camera of cameras) {
    if (route[0] <= camera && camera <= route[1]) {
      return true;
    }
  }
  return false;
}

참고

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