[알고리즘] 탐욕법(Greedy) 프로그래머스 3단계 - 단속카메라

def solution(routes):
    
    answer = 0
    status = [0] * len(routes)
    routes.sort(key=lambda x:x[1])
    
    for i in range(len(routes)):
        if status[i] != 0:
            continue
        for j in range(i, len(routes)):
            if routes[i][1] >= routes[j][0]:
                status[j] = 1
        answer += 1
    
    return answer

풀이과정

1. routes의 길이 만큼 상태를 저장하는 배열 status를 만든다.

• 원소 값이 1이면 단속 카메라를 만난 것이고 0이면 아직 만나지 않은 것이다.
• 끝나는 기점을 기준으로 routes를 정렬한다.

2. routes 배열을 for문을 돌리면서 i번째 인덱스를 검사한다.

• status의 i번째 인덱스가 1이면, 이미 단속 카메라를 만난 것이다.
• 아직 만나지 않았을 때, routes[i][1] >= routes[j][0]이면 겹치는 지점이 생긴 것으로 status 원소 값을 1로 바꿔준다.
• 단속 카메라를 만났기에 answer값을 1 올려준다.

ex) [-20, 15], [-18, -13]은 15 > -18 이기에 겹치는 부분이 생기고 단속 카메라를 1대 설치해주면 된다.