[Programmers] 단속카메라 (Python)

프로그래머스

문제

• 고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.
• 고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

구현

  

    
    
    
    
  
# 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇대의 카메라를 설치해야하는지
def solution(routes):
    routes.sort() # 들어온 지점에 따라 오름차순 정렬
    answer = 1 # 카메라 개수
    start, end = routes[0][0], routes[0][1]
    for i in routes[1:]:
        if start <= i[0] <= end:
            start = i[0] # 범위안에 있으면 시작점을 바꿔줌
            end = min(end, i[1])
        else:
            start, end = i[0], i[1]
            answer += 1 # 범위 안에 없기때문에 카메라 추가
    return answer

다른 풀이

  

    
    
    
    
  
# 역순으로 정렬해서 풀이
def solution(routes):
    answer = 0
    routes.sort(key=lambda x: x[0], reverse=True) 
    camera = 30001 
    print(routes)
    for route in routes:
        print(camera, route[1])
        if camera > route[1]:
            answer += 1
            camera = route[0]
    return answer