프로그래머스 카카오 고득점 kit - 탐욕법(greedy)

단속카메라

• 문제
• 코드
• 아래와 같이 풀려고 했는데 기준이 애매했다. 겹치는 자동차의 순서가 똑같다면 우선순위를 어떻게 할 것인가?
  6만의 도로 번호 각각은 구조체로 만든다
  각 도로 번호는 자동차 번호를 set으로 갖고 있다
  cnt 값도 갖고 있다 cnt는 자동차의 수
  compare를 cnt 기준으로 한다 ~~
  ~~그리 가장 자동차 수가 많은 것을 빼고
  모든 도로에 대해 해당 자동차를 빼주고
  다시 sort를 해준다.
• 다른 분의 풀이를 보고 푸는 방법을 알게 되었다.
  • routes를 진입지점을 기준으로 sort 한다.
  • 앞에서부터 하나씩 하는 과정
  • route 들을 하나씩 확인하면서 앞선 route의 범위에 들지 않으면 새로운 카메라를 설치하는 방식이다
  • 주의할 것은 이번차례에 확인하는 route의 end점이 기준으로 잡은 end 점보다 더 작으면 end점을 더 작은 값으로 갱신해 줘야 한다는 것이다.
  • 예를 들어 이렇게 있을 때는 1의 end 점으로 3은 커버할 수 있지만 2는 커버할 수 없다
• 프로그래머스에서 제공된 다른 분들 풀이 를 보고 end점을 기준으로 잡으면 더 단순하게 풀 수 있다는 것을 알게되었다. 이를 활용해 java를 풀었다
  • end점을 기준으로 sort한다.
  • end점에 카메라를 설치한다고 생각한다
  • 하나씩 확인하면서 route의 start가 end 점 보다 크다면 카메라를 새로운 route의 end점에 추가한다고 생각하면 된다