[프로그래머스] 단속카메라 (javascript)

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

프로그래머스

 

 

🤔 해결방법

1. routes를 자동차가 진입한 지점을 기준으로 오름차순 정렬
2. 첫 번째 자동차의 경로를 기준으로 카메라 개수를 1로 설정
3. if 모든 자동차 경로를 순회하면서 현재 처리 중인 자동차의 나간 시간보다 다음 자동차의 진입 시간이 크다면, camera+1 하고 현재 자동차의 enter, o을 다음 자동차의 값으로 업데이트
4. else if 다음 자동차가 현재 처리 중인 자동차 경로 범위 안에 있다면, 현재 자동차의 enter, o을 다음 자동차의 값으로 업데이트
5. 모든 자동차 경로를 확인한 후 설치된 카메라의 개수를 반환

 

 

🔑 풀이

지난 주에 풀었던 요격 시스템 문제와 매우 비슷한 문제라고 해서 복습할 겸 풀어봤다.

요격 시스템 문제와의 차이는 2가지가 있다. 

 

1. 구간이 음수이다.

요격 시스템 문제에서 미사일들의 구간이 모두 양수라 초기값을 [0,0]으로 잡고 시작했는데 이 단속 카메라 문제는 차량 구간이 모두 음수였다.

따라서 그냥 오름차순으로 정렬했을 때 오는 가장 첫 번째 차량의 구간을 초기값으로 잡아줬다.

그렇다면 camera 값도 1로 넣어줬다. 첫 번째 자동차의 나가는 지점에는 반드시 카메라가 필요하기 때문이다.

 

2. 개구간이 아닌 폐구간이다.

요격 시스템 문제에서는 구간들이 개구간으로 양 끝 값은 포함하지 않았다.

그런데 이 문제는 "차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다." 라는 조건이 있으며 이는 양 끝 값이 포함되는 폐구간을 의미한다고 볼 수 있다.

따라서 if 문인 '현재 처리 중인 자동차의 나간 시간보다 다음 자동차의 진입 시간이 크다면' 에서 크거나 같다면으로 할 필요가 없다. 

 

최종 풀이는 다음과 같다.

function solution(routes) {
      // 오름차순 정렬
      routes.sort((a,b) => a[0]-b[0]) // [[-20,-15],[-18,-13],[-14,-5],[-5,-3]]
      let camera = 1
      let [enter,out] = routes[0] // enter:고속도로에 진입한 지점, out:나간 지점

      for (const car of routes) {
          // 현재 처리 중인 자동차의 나간 시간보다 다음 자동차의 진입 시간이 크다면
          if (out < car[0]) {
              camera++ // 카메라 만남
              [enter,out] = car // 현재 자동차의 enter, out을 다음 자동차의 값으로 업뎃

          // 다음 자동차가 현재 처리 중인 자동차 경로 범위 안에 있다면
          } else if (enter <= car[0] && car[1] <= out){
              [enter,out] = car // 현재 자동차의 enter, out을 다음 자동차의 값으로 업뎃
          }
      }

      return camera;
  }

 

예제 1번을 그림으로도 표현해봤다.