[프로그래머스 42884 파이썬] 단속 카메라 (level 3, 그리디)

알고리즘 유형 : 그리디
풀이 참고 없이 스스로 풀었나요? : X

https://school.programmers.co.kr/learn/courses/30/lessons/42884

소스 코드(파이썬)

def solution(routes):
    answer = 0
    prev_end = -float("inf")
    
    for start, end in sorted(routes, key=lambda x: x[1]):
        if start <= prev_end:
            continue
        
        prev_end = end
        answer += 1
    
    return answer

풀이 요약

1. 그리디로 일반 해를 구할 수 있다.

   모든 도로를 진출 지점을 기준으로 오름차순 정렬한다.

   이 후 수행할 로직은 다음과 같다.

   변수 prev_end에는 가장 최근에 세워진 단속 카메라의 지점을 의미한다.

   정렬된 모든 도로를 차례로 순회하면서,

   1) 도로의 진입 지점이 prev_end보다 이전 혹은 같은 곳에 위치하면 이 도로는 prev_end를 거치므로 $^{설명1}$continue 해준다.

   2) 도로의 진입 지점이 prev_end보다 이후에 위치하면, prev_end 카메라는 이 도로 위에 위치할 수 없으므로 도로의 진출 지점에 카메라를 하나 새로 세워준다.

   설명1 : 도로의 진출 지점에 카메라를 세우므로, prev_end는 어떤 도로의 진출 지점과 같다. 이 때 모든 도로를 진출 지점 기준 오름차순 정렬했으므로, 순회 중인 A 도로의 진출 지점이 반드시 prev_end 카메라가 세워진 B 도로의 진출 지점(=prev_end)과 같거나 이후에 위치한다. 따라서, 순회중인 A 도로의 진입 지점이 prev_end 이하라면 prev_end는 반드시 A 도로 위에 위치하므로 continue하고 다른 도로로 순회를 넘어가는 것이다.

배운 점, 어려웠던 점

• 도로를 진입 또는 진출 지점으로 정렬하는 아이디어는 전에 경험했던 적이 있어서 생각해냈는데, 진출 지점에 카메라를 세우는 아이디어를 못 떠올렸다. 그리디 문제를 풀 때 너무 광범위하고 추상적으로 생각하는 것 같다.

  테스트 케이스를 직접 그려보고, 맨 처음 한 두가지의 데이터로 최선의 선택으로 최적해를 구하는 방법에는 어떤 것들이 있을지 고민하는 방식으로 접근하도록 연습하면 좋을 것 같다.