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

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

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

 

🍪 나의 풀이

def solution(routes):
    routes.sort(key=lambda x:x[0], reverse=True) # 시작점이 가장 큰 숫자부터 정렬
    # [[-5, -3], [-14, -5], [-18, -13], [-20, 15]]
    
    count = 0 # 결과
    camera = float('inf') # 카메라 위치는 임의로 가장 큰 숫자로 지정
    for i in range(len(routes)): 
        if routes[i][0] <= camera and camera <= routes[i][1]: # route의 범위 안에 카메라가 있으면 continue
            continue
        else: # 없으면 카메라의 위치를 바꾸고 count += 1
            camera=routes[i][0]
            count+=1
    return count

 

🍪 다른 사람 풀이

def solution(routes):
    # 진출지점을 기준으로 정렬 [[-18, -13], [-14, -5], [-5, -3], [-20, 15]]
    routes = sorted(routes, key=lambda x: x[1])
    last_camera = -30000

    answer = 0

    for route in routes:
        if last_camera < route[0]: # 진입지점이 last카메라 보다 뒤에 있으면
            answer += 1 
            last_camera = route[1] # 진출지점을 카메라로 지정

    return answer