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

 

나의 풀이

def solution(routes):
    routes.sort(key=lambda x: x[1])

    answer, last = 1, routes[0][1]

    for i in range(1, len(routes)):
        if routes[i][0] <= last <= routes[i][1]:
            continue
        else:
            answer += 1
            last = routes[i][1]

    return answer

 

 

뒤에서부터 푸는 풀이

def solution(routes):
    answer = 0
    routes.sort(key=lambda x: x[0], reverse=True) 
    camera = 30001 
    for route in routes:
        if camera > route[1]:
            answer += 1
            camera = route[0]
    return answer

 

 

겹치는 부분에 카메라 세우는 풀이

def solution(routes):
    routes.sort()
    length=len(routes)
    count=0
    cam=[0]*length
    camera=0
    for i in range(length-1,-1,-1):
        if cam[i]==0:
            camera=routes[i][0]#진입 지점
            count+=1
        for j in range(i,-1,-1):
            if cam[j]==0 and routes[j][1]>=camera:#이전 진입점(camera)이 현재 진출점보다 작거나 같다면 카메라 설치
                cam[j]=1 #카메라가 구간을 커버함
    return count