문제 보러 가기(programmers 42884)

문제 요약

고속도로를 이동하고 있는 차들의 진입 지점, 나간 지점들을 담고 있는 배열이 주어졌을 때 모든 차량이 최소 1번 단속카메라를 만나도록 하기 위해 설치해야 하는 카메라 수의 최솟값을 구해야 한다.

문제 풀이

설치할 카메라의 최소 개수를 구하기 위해서는 왼쪽부터 시작해서 고속도로를 나간 지점이 제일 앞에 있는 곳에 설치해주고 이 카메라에 포함되지 않은 차량 중에서 고속도로를 나간 지점이 제일 앞에 있는 곳에 또 설치해주는 식으로 구해주면 최솟값을 구할 수 있게 된다.(그리디 유형으로 접근)

코드

def solution(routes):
     # 마지막 카메라 위치 초기화
    last_pos = -30000
    # 끝 지점 기준으로 정렬
    routes = sorted(routes, key=lambda x: x[1])


    count = 0

    for route in routes:
        # 해당 구간이 마지막으로 설치된 카메라에 포착x
        if last_cam < route[0]:
            # 구간 끝 지점에 카메라 설치
            count += 1
            last_pos = route[1]

    return count

오른쪽부터 시작해서 고속도로 진입 지점이 제일 뒤에서 있는 곳에 설치해주는 식으로도 구현 가능..!(역으로 접근)
코드는 다음과 같다.

def solution(routes):
    # 마지막 카메라 위치 초기화
    last_pos = 30000
    # 진입 지점 기준으로 내림차순으로 정렬
    routes = sorted(routes, key=lambda x: x[0], reverse=True)

    count = 0

    for route in routes:
        # 해당 구간이 마지막으로 설치된 카메라에 포착x
        if last_pos > route[1]:
            # 구간 끝 지점에 카메라 설치
            count += 1
            last_pos = route[0]

    return count