단속카메라 ⁂

단속카메라
탐욕법(Greedy)
1720명 완료

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

코딩테스트 연습 - 단속카메라

시간제한이 없다면.. 

def solution(routes):
    cameras = set()
    while routes:
        all_case = {}
        for route in routes:
            for i in range(min(route), max(route) + 1):
                all_case[i] = all_case.get(i, 0) + 1
        max_ = max(all_case.values())
        for k, v in all_case.items():
            if v == max_:
                cameras.add(k)
                temp = []
                for each in routes:
                    if min(each) <= k <= max(each):
                        temp.append(each)
                for each in temp:
                    routes.remove(each)
                break
    return len(cameras)

이렇게 반복으로 풀 수 있겠지만.. 

근데 비싼 컴퓨터 샀으면..
이렇게 풀어야지.. ㅠ,.ㅠ
나의 머리는 소중한데...

def solution(routes): 
    camera = 30001 
    answer = 0 
    routes.sort(reverse=True) 
    for start, end in routes: 
        if end < camera: 
            camera = start 
            answer += 1 
    return answer

 

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