문제

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

풀이

시도 1

  • Greedy 탐욕법으로 가장 최적의 해를 구해야하는 문제
  • 나가는 순서를 기준으로 한줄로 정렬시킨다
  • 카메라 위치가 진입보다 작으면 카메라를 1대 더 설치하고 카메라는 나가는 위치에 설치한다 (어차피 나가는 기준으로 정렬했으므로)
solution.py 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def solution(routes):
    camera = -30001
    # 나간 기준으로 정렬
    routes.sort(key=lambda x: x[1])
    # 카메라 설치댓수
    cameraCount = 0
    # 자동차들의 루트를 돌면서
    for route in routes:
        # 진입하는 자동차가 카메라보다 앞에있으면
        if route[0] > camera:
            # 카메라 1대 더 설치
            cameraCount += 1
            # 나가는 순으로 정렬했기 때문에 나가는 위치에 카메라를 놓으면 됨
            camera = route[1]

    print(routes)
    return cameraCount