[알고리즘] 프로그래머스 단속카메라 파이썬 | 그리디

[프로그래머스] LEVEL3 단속카메라

문제

나의 풀이

def solution(routes):
    answer = 0
    routes.sort(key=lambda x:x[1])
    s = 0
    while s < len(routes):
        if s == len(routes) - 1:
            answer += 1
            break
        tmp = s
        for e in range(s+1, len(routes)):
            if routes[tmp][1] >= routes[e][0]:
                s += 1
            else:
                break
        answer += 1
        s += 1
    return answer

진출 시점을 기준으로 오름차순 정렬한다.
그 후 차량 A의 진출 시점과 차량 A보다 뒷 순서인 B의 진입 시점을 비교하는데,
A의 진출이 B의 진입보다 크다면 무조건 겹치는 구간이 존재한다. B의 진출은 무조건 A의 진출보다 늦기 때문 (정렬해서)
위 근거를 통해 그리디 알고리즘을 사용할 수 있었다.

처음에는 진입 시점 기준 오름차순 정렬을 했다.
테스트 케이스는 통과하였지만 제출했을 때 모두 오답이었다.
어쩐지 느낌은 그리디인데 내 풀이에 대한 근거가 없었다.

다른 풀이

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

내 풀이와 비교했을 때,

• answer를 먼저 증가시킴으로써 불필요한 코드 삭제 가능
• 인덱스 참조 대신 last_camera를 변경해줌으로써 단일 for문으로 구현

얻어가기

알고리즘의 근거를 찾자.