programmers.co.kr 코딩테스트 연습 > 탐욕법(Greedy) > 단속카메라

 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42884

 여러대의 차량의 고속도로 진입시점과 진출시점이 주어지고, 진입/진출 시점이 겹치는 부분을 찾아서,
단속카메라를 몇대를 설치할 것인지 개수를 알아내는 문제입니다.

 이 문제 처럼 X 축에 평행하는 여러개의 직선의 시작점과 끝나는 점이 주어지고,
이직선 들의 관계를 문제에서 주어진 조건에 따라서 푸는 문제들은 interval 카테고리에 해당합니다.

interval 카테고리의 문제를 풀 때, 조심해야 할 부분이, 어떤 직선의 시작점/끝나는 점이
다른 직선의 시작점/끝나는 점과 만났을 때, 어떻게 처리해야 하는지,
문제를 꼼꼼히 읽어 보아야 합니다.

• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난 것으로 간주합니다.

위와 같은 조건이 문제에 기술되어 있습니다. 따라서, 어떤 직선의 끝나는 점과 다른 직선의 시작점이

같으면 2개의 직선이 서로 만나게 되는 것입니다.

( * 이렇게 시작점과 끝나는 점이 만났을 때 도, 의미가 있는 경우를 폐구간 이라고 말하구요,

inclusive 라고 표현하기도 합니다. )

어떤 두대의 차량(A,B)이 모두 지나가는 고속도로 구간이 있는지 확인하려면

총 2가지 경우를 확인해 봐야 합니다.

1. A진입 <= B진출 <= A진출

2. B진입 <= A진출 <=B진출

두대의 차량(A,B)이 1~2 경우 중에 한개의 경우에 해당 한다면,

두대의 차량이 모두 지나가는 구간은 아래와 같이 계산할 수 있습니다.

 max(A진입, B진입), min(A진출, B진출)

특정구간(진입,진출) 을 지나가는 차량을 최대한 빨리 계산해 내기 위해서는,

진입, 진출 구간의 차이가 적은 순서로 정렬해야 합니다.

answers 는 이미 지나간 차량의 진입/진출이나, 2대 이상의 차량이 모두 지나가는 구간을
가지고있는 리스트 입니다. 초기값이 없으므로, 진입이 가장 빠른 차량을 넣어줍니다. 

    routes.sort()
    answers: List = [routes.pop(0)]

입력으로 주어지는 routes를 for 루프 에서 하나씩 꺼냅니다
앞에서 말한 2가지 경우에 해당하는지 확인하고, 2대의 차량이 모두 지나가는 구간을
min(), max() 함수를 사용해서 계산합니다.

from typing import List

def solution(routes: List[List]):
    if len(routes) == 0:
        return 0

    routes.sort()
    answers: List = [routes.pop(0)]

    for car_in, car_out in routes:
        prev_in, prev_out = answers.pop()

        if prev_in <= car_out <= prev_out \
            or car_in <= prev_out <= car_out:
            answers.append([max(prev_in, car_in), min(prev_out, car_out)])
        else:
            answers.append([prev_in, prev_out])
            answers.append([car_in, car_out])

    return len(answers)