[Programmers] 단속카메라

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

접근 방법

---

차량의 진출 순서를 기준으로 정렬하고, 앞에서부터 카메라를 설치해간다.

그리디 알고리즘을 활용할 수 있다.

• 예시에서 카메라는 다음과 같이 설치될 수 있다. 하지만 최대한 많은 차가 겹치도록 하기 위해서는 중간 보다는 진출 또는 진입시점에 설치하는게 좋다.

• 풀이에서는 진출 시점에 카메라를 설치했다.

• 자동차의 진출 시점에 카메라를 설치하는 과정을 살펴보면 다음과 같다.

---

풀이

---

def solution(routes):
    routes.sort(key = lambda x: x[1])   # 진출 시점을 기준으로 정렬한다.
    
    camera = routes[0][1]   # 가장 첫번째 차량의 진출 시점을 카메라 한개로 설정
    answer = 1
    
    for i in range(1, len(routes)):
        if routes[i][0] > camera:
            camera = routes[i][1]   # 현재 진출 시점에 카메라를 추가한다.
            answer += 1
        
    return answer

정리

---

• 그리디 알고리즘임을 알아도 풀지 못했다.

• 그리디 알고리즘: 현재 상황에서 지금 당장 좋은 것만 고르는 방법

• 그 아이디어를 떠올리기가 힘든 것 같다.

Uploaded by N2T