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

문제 설명

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

제한사항

• 차량의 대수는 1대 이상 10,000대 이하입니다.
• routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 - 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
• 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

풀이

그리디는 정렬부터한다
거의 다 풀었는데 끝끝내 안 풀려서 해답을 봐버렸다 ㅠ
내가 처음 풀었던 방법은 진입 시점을 기준으로 정렬하고
out을 가장 낮은 숫자로 갱신 하면서
out과 현재 자동차의 진입시점을 비교해 out보다 진입시점이 높으면 답을 추가하는 것이었다.

하지만 out을 갱신하는 방법이 잘 못 됐었다.
무조건 작은 것을 out으로 두는게 아니라
out보다 진입시점이 높으면 설치를 하고 out을 그 차의 끝지점으로 갱신하는 것이다.
그리고 다음차의 끝지점이 out보다 낮거나 같으면 겹치는 것이므로 out을 이 차의 끝지점으로 갱신해줘야 한다.

예를 들어

이렇게 정렬했다 치자

out은 5가 되고 진입시점인 3과 비교한다
두 지점이 끊어지지 않았으므로 out은 갱신 안되고 카메라도 설치할 필요 없다

다음 차를 보면 out뒤에 진입한다
따라서 카메라를 추가로 설치하고 out을 갱신해준다

다음차를 보면 out보다 끝지점이 더 낮다
이러면 카메라는 설치 안 하지만 out은 갱신해준다

마지막 차는 out보다 진입점이 높으므로 카메라도 설치하고 out도 갱신해준다.

따라서 원래 한개는 설치되었다치고(answer = 1로 초기화) 2개가 추가로 설치 되었으므로 총 3개가 필요하다

def solution(routes):
    answer = 1 # 1개는 무조건 설치 되어있다고 가정
    sortedRoutes = sorted(routes, key=lambda x: x[0]) # 정렬
    out = sortedRoutes[0][1] # 첫번째 차의 끝 지점을 out으로 지정
    for r in sortedRoutes[1:]:
        if r[0] > out: # out보다 현재차의 진입점이 높으면  
            answer += 1 # 카메라 설치하고
            out = r[1] # out 갱신
        if out >= r[1]: # out보다 현재차의 끝지점이 낮으면 겹치는 것이므로
            out = r[1] # out 갱신
    return answer