문제는 각 차량의 [진입 지점, 진출 지점]을 원소로 하는 routes라는 list가 주어졌을 때, 이 차량을 모두 단속하려면 최소 몇 개의 카메라를 설치해야 하는지 맞추는 문제이다. 즉, 중첩되는 지점을 체크해야 하는 문제이다. 나는 처음에 다음과 같이 풀이하였다.
routes 내 모든 차량을 조회하여 각 지점에 각 차량의 index를 push한다.
각 지점을 조회해서 가장 카운트가 많이 된 곳부터 순차적으로 index를 체크하며, 카메라를 카운트한다.
⇒ 이러한 풀이는 여러 반복문, 복잡한 코드로 이뤄졌다.
⇒ +) test case는 맞았으나 실제 정답은 틀렸다.
실제 정답 풀이는 다음과 같았다.
routes를 진출 지점을 기준으로 오름차순으로 정렬한다.
첫 key 값은 -30001로 주어진 문제의 범위 밖이다. ⇒ 여기서 key 값은 카메라의 위치로 간주할 수 있다.
반복문을 통해 routes의 원소들을 하나씩 조회하며, key 값보다 진입 시점이 큰지 비교한다.
3-2) 만약 진입 시점이 key 값보다 크다면, 해당 원소 이후의 원소들은 모두 앞선 카메라에 찍힐 수 없는 진입 시점을 갖고 있는 것이므로, 카메라를 하나 더 count한다. 그리고 key 값을 해당 route의 진출 시점으로 갱신한다.