[PROGRAMMERS]-단속카메라(Greedy)

📃 단속카메라

문제

고속도로를 지나는 차량의 대수는 1대 이상 10,000대 이하이며 각각의 차량은
-30,000 ~ 30,000의 구간 범위를 가집니다.

효율성 테스트도 함께 이루어지는 문제이기 때문에 시간복잡도, 공간복잡도를
고려하면서 해결해야 하는 문제이며 각 단계에서 최적해를 찾는
그리디 알고리즘을 적용하는 문제입니다.

풀이

1. 우선 routes배열을 나간시간기준 오름차순 정렬하면 다음과 같다. ([-18,-13], [-14,-5], [-5,-3], [-20,15])

2. camera 한개를 처음 나간차량의 나간시간에 설치한다. (-13)

3. 두번째 차량부터 들어온시간과 camera가 설치되어 있는 시간과 비교해서 들어온시간이 더 먼저이면

   다음 차량확인, 아니면 현재 차량의 나간시간에 다음 카메라를 설치하고 answer 1증가.

   • 두번째 차량의 들어온 시간이 camera1이 설치되어있는 시간보다 먼저이므로 넘어가고

   • 세번째 차량의 들어온 시간이 -13보다 늦으므로 camera2를 나간시간 -3에 설치한다.

   • 네번째 차량의 들어온 시간은 -3보다 먼저이므로 넘어간다.

4. 네번째 차량까지 모두 확인했으므로 answer을 return해준다.

코드

def solution(routes):
    answer = 1
    routes.sort(key= lambda x : x[1])
    camera = routes[0][1]

    for i in range(1,len(routes)):
        if camera < routes[i][0] : 
            answer += 1 
            camera = routes[i][1]

    return answer