단속카메라 (greedy)

문제

문제링크

나의 풀이

1. 우선 routes를 첫번째 index를 이용하여 sort하였다. 즉, 고속도로에 진입한 지점이 빠른 순으로 정렬한 것.
   
   
2. in / out이라는 변수를 이용하여 범위를 추적하였다.
   즉, -20 ~ -4가 이전 값이고 -> 다음 값으로 -13, 6이 들어오면 -> -13,-4를 각각 in, out에 저장한 것이다.
   
   
3. 해당 로직을 routes가 존재 할 때까지 계속 진행해주며, while이 돌 때마다 in, out을 초기화 한다.

def solution(routes):
    #1) sort
    routes = sorted(routes, key  = lambda x:x[0])  # 뒷걸음질....
    answer = 0
    
    while routes:
        # 2) cnt는 제거해야하는 index를 tracking 할 것이다.    
        cnt = 0
        i = routes[0][0]
        o = routes[0][1]
        
        for car in routes:
            if ( i <= car[0] and car[0] <= o) or ( o <= car[1] and car[1] <= o) :
                # in을 둘 중 작은 값으로
                i = car[0] if car[0] > i else i
                # out을 둘 중 큰 값으로
                o = car[1] if o > car[1] else o
                cnt += 1
        routes = routes[cnt:]
        answer += 1
    
    return answer

다른 사람의 풀이

풀고 정말 기뻤다. 그런데.....

def solution(routes):
    routes = sorted(routes, key=lambda x: x[1])
    last_camera = -30000

    answer = 0

    for route in routes:
        if last_camera < route[0]:
            answer += 1
            last_camera = route[1]

    return answer

??????????????????????????????????????????????????

위 코드는 나가는 위치를 기준으로 했다.
따라서 처음 차의 나가는 위치(최소값)에 카메라를 설치하고, 그 카메라에 걸리는 차들은 건너 뛰다가,
고속도로에 들어오는 위치가 해당 카메라보다 나중인 차가 나오면, 그 차의 나가는 위치에 카메라를 설치하는 식이다.
kia~