[프로그래머스 단속카메라] - Python 풀이

 

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

프로그래머스

---

문제 요약

 모든 차량이 카메라를 한번은 만나도록 카메라를 설치한다. 이때 최소 몇 개의 카메라를 설치해야 하는가?

---

풀이

  문제에서 시작점 혹은 도착점에 카메라를 설치해도 된다고 하였으므로, 도착점 혹은 시작점에 카메라를 설치하는 게 카메라가 다른 차도 찍게 될 가능성을 높이는 방법이다. 

풀이 과정은 다음과 같다.

1. 계산의 편의를 위해 입력 배열 routes를 도착점을 기준으로 오름차순으로 정렬해준다.

2. 카메라 설치 위치를 저장할 배열 camera를 선언해준다.

3.  routes의 각 차량들에 대해 for문을 돈다.

  3.1. 만약 카메라가 아예 없는 상태라면 첫 번째 차량의 도착점에 카메라를 추가해준다.

  3.2. 만약 설치된 카메라가 차량의 시작점보다 작다면, 즉 설치된 카메라가 현재 차량을 포착하지 못하는 상황이라면, 현재 차량의 도착점에 카메라를 설치해준다. (camera 배열에 end 추가)

4. camera 배열의 길이를 리턴해준다.

def solution(routes):
    """
    모든 차량이 카메라를 한번은 만나도록 카메라를 설치한다.
    이때 최소 몇 개의 카메라를 설치해야 하는가
    """
    routes.sort(key=lambda x: x[1])
    
    camera = []
    for route in routes:
        start = route[0]
        end = route[1]
        
        if not camera:
            camera.append(end)
            
        if camera[-1] < start:
            camera.append(end)
        
    return len(camera)