[Programmers 코딩테스트 고득점 Kit] 단속카메라

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/42884

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

차량의 대수가 최대 10,000대이므로 O(N^2)으로는 풀 수 없는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. routes 벡터를 차량이 고속도로에 진입한 지점을 기준으로 오름차순 정렬을 합니다.

2. 첫 번째 차량의 고속도로 탈출 지점에 카메라를 설치합니다.

3. 두 번째 차량부터 고속도로 진입한 지점과 기존 카메라 설치 지점을 비교합니다.

3.1 진입한 지점이 기존 카메라 설치 지점보다 앞서면 굳이 카메라를 추가로 설치하지 않아도 됩니다. 따라서, 다음 카메라 설치지점을 min(기존 카메라 설치 지점, 해당 차량이 고속도로에서 나가는 지점)으로만 표시해둡니다.

3.2 진입한 지점이 기존 카메라 설치 지점 이후라면 3.1에서 기존에 표시해놓은 카메라 설치 지점에 카메라를 설치하고 다음 카메라 설치 지점을 해당 차량이 고속도로 나가는 지점으로 표시해둡니다.

4. 3번 과정을 두 번째 차량부터 마지막 차량까지 진행해줍니다.

5. 카메라 개수를 반환해줍니다.

 

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~