[Level 3] 단속카메라

programmers.co.kr/learn/courses/30/lessons/42884

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

---

접근

탐욕법 알고리즘에 분류된 문제이다. 그래서 어떠한 기준으로 매번 최적을 선택할지 고민을 했다.

먼저 정렬을 했는데 진입한 시점을 기준으로 오름차순으로 정렬을 하였다. 이후 규칙을 찾아보려고 했고 나가는시점을 기준으로 오름차순 정렬도 해보았다. 

나가는시점을 기준으로 정렬했을 때 나가는 시간을 기준으로 카메라를 설치하고자 하였다.

 

즉, 정렬 후에는 첫 번째 오는 시간은 가장 빨리 나가는 차량이기때문에 해당 차량이 나가는 시점에 카메라를 설치한다. 이후 설치한 카메라의 시점을 통해 다른 차량들의 정보를 탐색하여 진입시점과 나가는시점 사이에 설치한 카메라가 있으면 계속해서 탐색하고 사이에 없다면 새롭게 카메라를 설치해준다. 이때 카메라를 설치하는 시점은 차량이 나가는 시점이다.

 

구현

먼저 입력된 routes를 나가는 시점을 기준으로 오름차순 정렬을 하였다. 

그리고 가장 빨리 나가는 차량의 시점에 카메라를 한 대 설치하고 이를 기준으로 탐색을 진행한다.

차량의 정보들을 통해 비교하여 현재 설치한 카메라가 해당 차량이 진입시점과 나가는 시점 사이라면 계속 진행해주고 아니라면 카메라를 새롭게 갱신해준다.

 

카메라 갱신은 현재 설치된 카메라로 못잡는 차량이 나가는 시점에 새롭게 설치하고 answer를 증가시킨다.

def solution(routes):
    answer = 1
    routes = sorted(routes, key=lambda x: x[1])
    flag = routes[0][1]
    for a, b in routes:
        if a <= flag <= b:
            continue
        else:
            flag = b
            answer += 1
    return answer