[Algorithm] 단속카메라

📋 문제

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

 

제한 사항

• 차량의 대수는 1대 이상 10,000대 이하입니다.
• routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
• 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

 

입출력 예

[[-20,-15], [-14,-5], [-18,-13], [-5,-3]]

2

 

✏️ 풀이

가장 접근했던 방법은 일일히 표시를 하는 방법이었다. 길이 60000의 배열 두고 이 구간을 지나갔는지 확인을 하면서 처음 지나가는 길이라면 answer를 증가시켜주는 방법이다. 하지만 생각해보니 들어온, 나간 시점을 순회해줘야 하는데 [-30000, 30000] 같은 값이 많이 들어오면 당연히 시간초과가 나겠다고 생각해서 시도하지 않았다. 이 방법을 생각하다가 이전 차가 나간 시점보다 다음 차가 들어올 때 작다면 그때는 카메라를 설치하지 않아도 되는구나를 깨닫게 되었다. 도로를 나간 시점을 기준으로 하기 때문에 정렬시켜주고 초기 비교값(나간시점)을 최소값 -30000으로 초기화했다. 반복문으로 현재 비교값보다 차가 들어온 시점이 크다면 겹치는 부분이 없기 때문에 카메라를 추가하고 비교값을 나간 시점으로 변경시켜줬다.

 

 

⌨️ 코드

function solution(routes) {
  var answer = 0;
  let compare = -30000;

  routes.sort((a, b) => a[1] - b[1]);

  for (const route of routes) {
    const [start, end] = route;

    if (compare < start) {
      answer += 1;
      compare = end;
    }
  }

  return answer;
}