[프로그래머스] 단속카메라 (Python3)

programmers.co.kr/learn/courses/30/lessons/42884

코딩테스트 연습 - 단속카메라

def solution(routes):
    answer=0
    visited=[False]*len(routes)
    routes.sort()
    for i in range(len(routes)-1,-1,-1):
        if not visited[i]:
            answer+=1
            camera=routes[i][0]
            visited[i]=True
            for j in range(i-1,-1,-1):
                if not visited[j] and routes[j][0]<=camera<=routes[j][1]:
                    visited[j]=True
    return answer

어려워서.. 구글링 해서 해답보고 풀었다!

오랜만에 푸는 Greedy(탐욕법) 문제.

처음에는 route 간의 교집합의 개수를 계산하는 방식으로? 풀려고 했다가 빵점 당첨 ^~^

옳게 푸는 해결 방법은 이렇다.

1. 각 route들을 오름차순으로 정렬해서 가장 오른쪽에 있는 것의 진입로에 카메라를 세운다. 이때 answer을 +1해준다.

2. 왼편에 있는 route들 중에서 그 전까지 카메라를 보지 않았으며(visited가 False인), 루트 안에 카메라가 있는지 체크하여 조건을 만족하는 경우 visited를 True로 설정한다.

이런 과정을 모든 route마다 반복한다.