99클럽 코테 스터디 17일차 TIL - 42884 단속카메라

42884. 단속카메라 / c++ / level3 / 32분

문제 및 코드

접근 방식

그리디 / 정렬 / 라인 스위핑

1. 이런 문제는 일단 시작점과 끝점 양쪽을 기준으로 빠른 순으로 정렬한다.
2. 그러면 모든 차(선분)이 겹치거나 겹치지 않는 형태로 일렬로 정렬이 된다.
3. 정렬된 벡터를 순회하면서, 만약 두 차의 경로가 겹친다면, 겹치는 부분으로 합친다.
   ([-20, -15], [-18, -13] 인 두 차량의 경우 [-18, -15]로 합친다.)
4. 그러다 겹치지 않는 차량이 나오면, 이전까지의 겹친 차량들은 카메라가 필요하므로 answer++
5. 그렇게 모든 차량을 순회하여 나온 answer를 반환한다.

생각해 볼 점

1. 처음엔 두 차량의 경로를 비교해서 겹친다면 합칠 때 경로의 끝 지점을 두 경로 중 큰 값으로 정했었는데, ([-20, -15], [-18, -13]인 경우 [-20, -13] 로 지정)
   이 경우, 1번 경로가 2번, 3번 경로보다도 커서, 3번을 포함하는 부분에 카메라를 설치하게 되면, ( 예시 : 1[ 2[ ] 3[O] ] ) 1,3번은 영향을 받지만, 2번은 놓치게 된다.
   그래서 겹치는 부분이 존재한다면 [두 차의 경로의 시작 값 중 큰 수] 부터 [두 차의 경로의 끝 값 중 작은 수] 로 경로를 합쳐야 놓치는 차량이 없이 카메라를 설치할 수 있었다.

해시태그

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL