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

사용 언어 - Python3

문제 - 단속카메라

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

프로그래머스

 

 

정답

그리디

진출 시점을 기준으로 그 다음 진입시점이 진출시점보다 작다면, 안 겹치는 구간!

안겹치는 조건 = route[0] > key(진출시점)

[[-20, -15], [-18, -13], [-14, -5], [-5, -3]]

-20 >-30001 (True. 안겹친다)

answer = 1

key = -15

 

-18 > -15 (False. 겹친다)

 

-14 > -13 (False. 겹친다)

 

-5 > -5 (True. 안겹친다)

 answer = 2

key = -3

def solution(routes):
    routes.sort(key = lambda x:x[1]) # 진출시점 기준으로 정렬
    key = -30001 # 최저 key
    answer = 0
    
    for route in routes:
        if route[0] > key: # 현재 진입시점 > 그 전의 진출시점 = 안겹침
            answer += 1 # cctv 한 개 더 필요
            key = route[1] # 다음 진출시점으로 업데이트
    
    return answer

 

 

 

레퍼런스

https://velog.io/@jqdjhy/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%8B%A8%EC%86%8D%EC%B9%B4%EB%A9%94%EB%9D%BC-Greedy

[프로그래머스, 파이썬] 단속카메라, Greedy

https://hbj0209.tistory.com/104

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