알고리즘 스터디 - 프로그래머스 : 단속카메라

문제 해석

목적 : 모든 차량이 단속용 카메라를 적어도 한번 만나도록 카메라 설치하기

해석
1. routes라는 차량의 경로가 있는 배열이 주어짐
2. 1 <= car <= 10000
3. routes[i][0] = i 차량이 고속도로에 진입한 지점, routes[i][1] = i 차량이 고속도로에서 나간 지점

어떤 알고리즘을 써야할까?

예시 : [[-20,-15], [-14,-5], [-18,-13], [-5,-3]]

1. 진입시점이 내림차순으로 정렬
2. 맨 낮은 경우부터 겹치는 지점을 계산해서 지점을 추가
3. 겹치는 지점에 대하여 다음 차량도 겹치는 구간이 있는지 계산 있다면 기존 지점에 추가
4. 겹치지 않는다면 새로운 차량부터 계산하여 지점을 추가함
5. 끝 지점까지 계산하여 최종 지점 추가

알고리즘 코드

def solution(routes):
    answer = 1
    # 내림차순으로 정렬
    routes.sort(key=lambda x:x[0], reverse=True)
    
    now = routes[0][0]
    for i in routes[1:]:
        # 겹칠 경우
        if i[1] >= now:
            continue
        # 겹치지 않을 경우
        else:
            now = i[0]
            answer += 1
    
    return answer