[프로그래머스] LV.3 단속카메라 (JS)

문제

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

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

제한

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

입출력 예시

routes	return
[[-20,-15], [-14,-5], [-18,-13], [-5,-3]]	2

풀이

역시 Greedy 하게 접근이 가능한 문제이다. 해당 문제는 별도로 효율성 테스트도 있으므로 약간의 발상의 전환으로 반복문을 하나만 써서 O(N)으로 문제를 풀어보도록 하자.

먼저 카메라를 어떻게 최소로 설치할 수 있을지 잘 생각해보자. 해당 정보에 접근하기 위해 일단 우리는 먼저 고속도로에 각 차량이 언제 진입을 했는지 파악해야 한다. 이때 각 차량의 진입 시점을 기준으로 오름차순 정렬(더 빨리 진입한 순)한다면 Greedy 하게 접근하기 용이하다.

그 까닭은 먼저 진입한 차량의 진출 시점과, 다음 차량의 진입 시점으로 우리는 두 차량을 체크하기 위해 설치할 카메라의 개수가 따로따로 필요한지 중복이 가능한지를 구분할 수 있기 때문이다.

위 그림으로 자세히 살펴보자. 위 그림은 차량의 진입 시점을 기준으로 오름차순 정렬한 상태와 같다. 즉 빨간 차량 -> 초록 차량 -> 파란 차량 -> 갈색 차량 순으로 고속도로에 진입했다는 것을 알 수 있다.

여기서 빨간 차량과 초록 차량을 먼저 비교해보자. 빨간 차량의 진출 시점은 -15 이고, 초록 차량의 진입 시점은 -18 이다. 즉 빨간 차량의 진출 시점 > 초록 차량의 진입 시점 이다. 이 경우 항상 이전 차량이 빠져나가기 전에 현재 차량이 진입하기 때문에 카메라 1대로도 이 시점의 차량들을 모두 체크할 수 있다.

마찬가지로 현재 차량이 이전 차량의 진입 - 진출 시점 간격 사이에 내포되어 있다면 역시 카메라 1대로도 이전 차량과 현재 차량을 모두 체크할 수 있다.

그렇다면 언제 카메라가 설치되어야 할까? 이전 차량의 진출 시점 < 현재 차량의 진입 시점 이 되는 순간 두 차량은 접점이 없기 때문에 각각 카메라가 필요하다.

위의 조건들을 정리하면 다음과 같다.

1. 이전 차량 진출 시점 < 현재 차량 진입 시점

   • 카메라 1대 추가 설치
   • 진출 시점 = 현재 차량의 진출 시점으로 갱신

2. 이전 차량 진출 시점 > 다음 차량 진출 시점

   • 진출 시점 = 현재 차량의 진출 시점으로 갱신

2번 조건이 중요하다. 일단 2번 조건에서는 현재 차량이 이전 차량의 범위 내에 항상 존재한다는 것이 보장된다. 즉 카메라는 추가로 설치하지 않아도 된다. 그러나 진출 시점은 현재 차량의 진출 시점으로 갱신되어야 하는데, 이는 다음 차량이 설령 첫 차량의 구간 범위내에 완전히 내포된다고 할 지라도 현재 차량과의 접점이 없다면 카메라를 또 추가로 설치해야 하기 때문이다. 말로 하면 어렵지만 그림으로 나타내면 다음과 같다.

위 그림처럼 초록 차량과 파란 차량은 모두 빨간 차량이 진입하고 진출하기까지 그 구간 범위 내에서 진입과 진출이 이루어졌다. 이때 첫 진출 시점은 빨간 차량의 진출 시점으로 초기화 되어 있고, 이를 다시 초록 차량의 진출 시점으로 갱신하지 않는다면 파란 차량에 카메라를 설치해야 한다는 것을 체크할 수 없다. 따라서 지금 진출 시점이 다음 차량 진출 시점보다 크다면 항상 진출 시점의 값을 갱신해주어야 한다.

해당 작업을 모두 마치고 주의사항이 하나 더 있다. 위와 같이 카메라 설치 개수를 모두 체크하면 항상 정답보다 1이 부족하다. 이는 관점에 따라 크게 두 가지로 생각이 가능한데

1. 첫 차량의 카메라 설치 여부를 체크하지 않았다.
2. 마지막 차량의 카메라 설치 여부를 체크하지 않았다.

두 가지 다 맞는 소리이다. 만약 1번 관점으로 생각하여 접근한다면 answer = 1로 시작하면 될 것이고, 후자의 경우엔 return answer + 1로 접근하면 될 것이다.

설명이 장황한데 코드로 보면 이해가 더 쉬울 수 있다. 전체 코드는 다음과 같다.

코드

function solution(routes) {
  let answer = 1;  // 1번 관점으로 접근
  
  routes.sort((a, b) => a[0] - b[0]);
  // 진입 시점을 기준으로 오름차순 정렬
  
  let out = routes[0][1];
  // 첫 진출시점(out)은 첫 차량의 진출시점으로 초기화
  
  for(let i = 1; i < routes.length; i++) {
    // 진출시점보다 현재 차량의 진입이 느리다면
    // 카메라 추가 설치 및 out 시점 갱신
    if(out < routes[i][0]) {
      answer++;
      out = routes[i][1];
    }
    
    // 진출시점이 현재 차량의 진출시점보다 큰 경우
    // 항상 out을 갱신해주어야
    // 다음 차량 카메라 설치 여부 판별 가능
    if(out > routes[i][1]) {
      out = routes[i][1];
    }
  }
  
  return answer;
}

출처

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