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

단속카메라

---

풀이과정

• 하나의 카메라가 최대한 많은 차량을 만나도록 해야 설치하는 카메라를 최소로 할 수 있다.

1. routes 리스트를 진입 지점 기준으로 정렬한다.
2. 카메라가 최대한 많은 차량을 만나게 되는 구간의 시작 지점과 끝 지점을 각각 start 변수와 end 변수로 저장한다. start 변수는 -30000으로, end 변수는 30000으로 초기화한다.
3. routes 리스트를 for문을 돌린다. start를 현재 차량의 진입 지점으로 업데이트한다. 만약 이 업데이트한 start가 end보다 크면 하나의 카메라로 커버 가능한 구간이 끝난 것이므로 answer에 1을 더하고 end를 현재 차량의 진출 지점으로 업데이트한다. 그렇지 않은 경우에는 현재 차량의 진출 지점이 end보다 작을 때만 end를 현재 차량의 진출 지점으로 업데이트한다. 마지막 구간에서 카메라를 더하는 부분이 없으므로 answer에 1을 더한 값을 리턴한다.
   ex. routes = [[-20,15], [-18,-13], [-14,-5], [-5,-3]]일 때 카메라를 설치해야하는 구간은 [-14,-13], [-5,-3]이다. 위 방식으로 [-14,-13]구간을 구하고 for문이 [-5,-3] 차량으로 넘어갈 때 더이상 하나의 카메라로 커버가 불가능하므로 answer에 1을 더한다. [-5,-3] 차량의 다음 차량이 없어서 for문에서는 [-5,-3] 구간의 카메라를 추가하는 부분이 실행되지 않으므로 마지막에 answer에 1을 더한다.

Python Code

def solution(routes):
    answer = 0

    routes.sort(key=lambda x:x[0])
    print(routes)
    
    start = -30000
    end = 30000
    for i in routes:
        start = i[0]
        if start>end:
            answer += 1
            end = i[1]
        if i[1]<end:
            end = i[1]
        
    return answer+1

오류와 해결

집합 커버 문제를 활용해서 풀어보려고 했는데 시간 초과가 나서 for문을 하나쓰는 위 방법으로 바꿨다.