<Level 3> 단속 카메라 with JS

 

문제 설명

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

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

 

제한사항

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

 

function solution(routes) {
  routes.sort((a, b) => a[0] - b[0]);
  const result = [routes[0]];
  for (let i = 1; i < routes.length; i++) {
    let isContain = false;
    for (let j = 0; j < result.length; j++) {
      if (result[j][1] >= routes[i][0]) {
        // 시작점이 범위 안
        result[j][0] = routes[i][0];
        result[j][1] = Math.min(result[j][1], routes[i][1]);
        isContain = true;
        break;
      }
    }
    if (!isContain) result.push(routes[i]);
  }
  return result.length;
}

 

 - 위는 처음에 풀었던 방식이다. 정말 최악의 경우 n^2 복잡도를 갖게되므로 좋지 않은 풀이이다. 

 

 - 먼저 정렬을 하였고, 하나씩 탐색한다. result는 카메라를 놓을 수 있는 범위이며, 길이가 곧 카메라 댓수이다.

 

 - 먼저 들어간 범위보다 작은 범위를 갖는다면 이 범위에 카메라만 설치하더라도 앞의 차량은 카메라를 만나게 된다. 따라서 작은 범위를 가지면 result 배열을 업데이트한다. 

 

 - 만약 result 배열을 모두 탐색했지만 카메라가 속할 수 있는 범위를 찾지 못하면  새로운 카메라를 설치해야하는 것이므로 result에 범위를 push한다.

 

 - 위와 같이 제출한 후 정답판정을 받았고, 다른 사람의 풀이를 보고 for문 하나로도 풀 수 있다는 것을 알게되었다. 그래서 개선한 코드는 다음과 같다.

 

function solution(routes) {
  let answer = 0;
  routes.sort((a, b) => a[0] - b[0]);
  let camera = -30001;
  for (let route of routes) {
    if (route[0] > camera) {
      camera = route[1];
      answer++;
    } else {
      camera = Math.min(camera, route[1]);
    }
  }
  return answer;
}

 

- 시간복잡도는 정렬에 의해 n log n 으로 예상된다.

 

 - 로직자체는 처음 풀었던 코드와 동일하다. 하지만 처음 풀었던 코드는 정렬을 했음에도 이를 제대로 활용하지 못했던 것 같다.

 

 

---

 

참고

 

코딩테스트 연습 - 단속카메라