[Programmers]Lv 3. 단속카메라

문제:

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

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

문제 풀이:

프로그래머스에서 이 문제의 태그를 탐욕법으로 걸어 놓았으니 탐욕적으로 풀려고 한다. 탐욕적인 방법은 말 그래도 욕심을 부려서 최고의 결과를 얻고자 하는 방법이다.( 물론 항상 얻는다는 보장은 없다.!) 따라서 이 문제에서 적게 쓰고 최고의 결과를 얻기 위해서는 차량의 진출입로에 단속카메라를 설치하는 것이 가장 최상의 방법일 것이다. 

따라서 각 차량이 단속카메라에 만났는지 확인하는 check 배열을 만들었고, 임의로 설치한 단속카메라를 만났다면 1로 바뀌도록 하였다. routes를 정렬을 하고 뒤에서부터 진입로에 카메라를 설치해 나가도록 하였다. 

처음에는 -5에 설치를 하고 이 카메라가 확인할 수 있는 다른 차량을 확인해보았을 때. [-14,-5]와 [-20, 15]가 이 카메라로 확인을 할 수 있으니 이 차량들의 check도 1로 바꾼다. 그 다음에는 -18에 설치를 해서 [-18, 13]의 check도 1로 바꾸도록 한다. 따라서 2 개의 단속 카메라가 필요하게 된다.

ps) 뒤에서부터가 아닌 앞에서부터 하려고 했으나 통과를 하지 못해서 하지 못하였습니다.

def solution(routes):
    routes.sort()
    answer = 0
    check =[0]*len(routes)
    for i in range(len(routes)-1,-1,-1):
        if check[i]==0:
            camera = routes[i][0]
            answer+=1
        for j in range(i,-1,-1):
            if check[j]==0 and routes[j][1] >= camera >=routes[j][0]:
                check[j]=1
    return answer