[프로그래머스] 탐욕법(Greedy) - 단속카메라

 

 

 

나의 답

def solution(routes):
    routes.sort() #정렬
    
    location = routes[0][1] # 카메라의 끝지점 설정 
    camera = 1 # 카메라 개수
    
    for start, end in routes[1:]:
        # 새로운 차량의 시작시점과, 기존 카메라의 끝 지점 비교
        if location <start: # 기존 카메라가 담아내지 못하니, 새롭게 시작
            camera+=1 
            location = end
        else: # 기존 카메라가 담아낼 수 있음, 끝 위치 조정(기존 카메라, 새로운 차량 끝 부분)
            location = min(end,location)
            
    return camera

 

하하 어려웠다...

생각보다는 간단했을 지도 ?? 싶지만

location은 카메라 범위의 끝 부분이다.

 

카메라가 담을 수 있는 범위에 속하면, 다시 기존에 있던 끝 부분과 새로 감시하게 된 차량의 끝 부분을 조정한다.

왜냐면, 그 뒤에 새로 감시할 차량들과 그 전에 있는 차량들을 모두 확인할 수 있는 범위일려면 끝 부분을 조정해서 다 담아낼 수 있도록 해야하기 때문이다.

 

카메라가 담을 수 없는 범위라면, 새로운 카메라를 마련하여 또 다시 끝 부분을 담아준다~ 이런 식으로 계속 반복 !

 

location 조정하는 거에서 왜 틀렸나 싶었는데 이유가 있었다.

좀 더 유연하게 생각할 수 있도록 문제를 많이 풀어봐야겠다. 

 

그리디는 진짜 직접 그려보면서 해야되겠다...^^

 

다른 사람 답

거의 비슷해서 이번에는 패쓰