[프로그래머스] 그리디 - 단속카메라, 파이썬

문제

---

• 프로그래머스 문제 링크
• routes 배열에 각 차량의 진입, 진출 시점이 주어지는데 모든 차량을 감시할 수 있는 최소 카메라의 수를 리턴하는 문제

풀이

요구역량

• 레벨 3
• 그리디(아이디어)

---

• 프로그래머스에는 그리디 알고리즘 문제로 분류되어 있다.
• 그리디 알고리즘은 각 단계에서 최선의 선택(논리적으로 합당한)을 이어나가며 문제를 해결하는 방법인데 아이디어가 떠오르면 쉽게 풀리는 경우가 있다.
• 주어진 routes 배열을 진출시점(=진출 위치, 좌표로 판단)을 기준으로 정렬해 준 후 체크되지 않은 첫 번째 차량의 진출위치를 camera 변수에 담아준다.
  (모든 차량을 체크해야 하기 때문에 가능한 뒤쪽에 카메라를 설치하는 선택 = 그 시점에서의 최선의 선택)
• 해당 카메라 위치 전에 진입하는 차량들은 모두 패스해준다.
• 만약 현재 카메라에 위치 뒤쪽으로 오는 차량이 있다면 ret(no. of camera) 에 1을 더해주고 이를 반복해준다.

코드

def solution(routes):
    routes.sort(key = lambda x : x[1])
    camera = routes[0][1]
    ret = 1
    for route in routes :
        if route[0] <= camera :
            continue
        else :
            camera = route[1]
            ret += 1
    return ret