[프로그래머스] 단속 카메라

문제

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

프로그래머스

 

---

 

주요 아이디어

• 유형만 알아두면 정말 쉬운 문제!
• 비슷한 문제로 프로그래머스 요격 시스템이 있다
• [진입 시점, 진출 시점]을 입력 받고, 모든 차량이 한 번씩 단속카메라를 만나도록 할 때 최소 몇 대를 설치해야 할까?
• 자동차가 도로에서 사라지는, 진출 시점을 기준으로 정렬
• 카메라를 한 대씩 추가하면서 현재까지 설치된 단속 카메라의 범위를 갱신해주기

 

---

 

코드 구현 (Python 3)

 

def solution(routes):
    answer = 0
    # (진입 시점, 진출 시점)
    # 진출 시점 기준으로 정렬 잡고
    routes.sort(key=lambda x:x[1])
    cam = -30001 # 초기 위치 설정
    
    for route in routes:
        # 감시카메라가 진입시점보다 작을 경우 못 만난 것
        # 감시카메라 한 대 추가하고 감시카메라 위치 진출 시점으로 변경
        if cam < route[0]:
            answer += 1
            cam = route[1]
    
    return answer

 

 

 

---

 

제출 결과