프로그래머스. 단속카메라

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

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

 

모든 차의 이동 범위에 단속카메라를 설치하는데, 최소로 설치할수 있는 갯수가 몇개인지 찾는 문제다.

 

주어지는 루트 배열이 다음과 같다

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

 

우선 가장 먼저 들어온 차 부터 체크해보자. [-20,-15]

모든 차들의 범위를 커버해야 하므로 일단 처음으로 지을 카메라는 무조건 [-20,-15] 지점에 설치되어야 한다.

그런데 우리는 카메라의 개수를 최소로 설치해야 하므로, 이 범위에 포함되면서 최대한 다른 차들도 커버되도록 설치해야한다.

 

다음으로 진입하는 차를 보면 [-18,-13]이다.

만약 처음차가 들어왔을때 처음차가 진출하는 시점인 -15에 설치했다면

두번째 차의 범위까지 포함된다.

그럼 이번에도 마찬가지로 카메라 위치를 두번째 차가 진출하는 시점인 -13으로 옮겨야 할까?

아니다. 그렇게 되면 카메라가 첫번째 차의 범위에서 벗어나게 된다.

카메라의 위치는 두 차 모두 포함되어야 하므로,

첫번쨰 차가 진출하는 시점(-15)과, 두번째 차가 진출하는 시점(-13)중 작은 값이 카메라의 위치가 된다.

 

따라서 문제를 풀때는 진입시점 기준으로 오름차순 정렬한 후,

큐에 삽입하고,

큐의 front 요소, 즉 먼저 들어온 차 부터 탐색한다.

카메라의 위치는 현재 탐색중인 차의 진출 시점이고,

pop하면서 차의 진입시점이 현재 카메라의 위치보다 크다면 새로운 카메라를 설치해준다.