단속 카메라 with 파이썬

- 포함 관계에 대한 이해 필요

# return 최소 카메라 설치 갯수

# 차량: 1~ 10000
# [진입, 진출]
# 진입, 진출 지점에 카메라 설치도 만난 것
# -30000 ~ 진입, 진출 ~ 30000

# 교점이 많은 부분에 설치하는게 이득
from copy import deepcopy

def solution(routes):
    answer = 0
    n = len(routes)
    check = [0] * n
    start = sorted(routes, key=lambda x: x[0])[0][0]
    end = sorted(routes, key=lambda x: x[1])[-1][1]

    checked = set()
    # 전체 구간
    for idx in range(start, end+1):
        new_checked = deepcopy(checked)
        # for i,s,e in enumerate(routes): -> 에러
        # 특정 구간에서 감시 가능한 차 체크
        for i, v in enumerate(routes):
            if v[0] <= idx <= v[1]:
                checked.add(i)
        # 모두 커버 가능한 경우 종료
        if len(checked) == n:
            return answer

        # 집합 관계로 문제 풀이해야 함
        if checked != new_checked :
            pass
        else:
            answer += 1

 

 

 

# 1. 포함 관계를 확인하기 위해 routes 배열을 오름차순 정렬

# 2. 이미 시작점 기준으로 오름차순으로 정렬되어 있기 때문에, 앞의 인덱스의 도착점(standard)가 다음 경로의 시작점보다 크면 포함관계

# 3. 2에서 포함관계를 찾았을 때, 그 안에 또 포함관계가 생겨날수 있기때문에, 계속 탐색. 대신 standard (도착점)을 비교해주어 더 작은 수로 갱신 시켜준다.

def solution(routes):
    answer = 0
    routes.sort()

        # 도착점
    standard = routes[0][1]
    routes.pop(0)
    answer += 1

    for item in routes:
                # 다음 차의 시작점이 현재 기준점 보다 작은 경우 포함 관계 성립
        if item[0] <= standard:
                        # 기준점 더 작은 값으로 재설정
            standard = min(item[1], standard)
                # 포함관계 아닌 경우 카메라 추가
        else:
            standard = item[1]
            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