프로그래머스 - 단속카메라 (Greedy) / Level 3

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

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

 

문제 설명

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

 

 

제한 사항

• 차량의 대수는 1대 이상 10,000대 이하입니다.
• routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난 것으로 간주합니다.
• 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

 

입출력 예시

routes	return
[[-20,15], [-14,-5], [-18,-13], [-5,-3]]	2

 

입출력 예 설명

 

-5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.

-15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.

 

 

풀이

def solution(routes):
    answer = 1
    
    routes.sort(key=lambda x : x[1])  # 차를 나간순서대로 정렬.
    camera = routes[0][1]  # 카메라를 차가 가장 먼저 나간 지점에 배치.
    
    for i in routes:
        if camera < i[0]:  # 현재 카메라 지점 이후에 들어온 차량이 있으면
            camera = i[1]  # 그 차량이 나간 지점에 카메라 배치.
            answer += 1
    
    return answer

처음 풀었을 땐 모든 경우를 체크해서 풀려고 했는데 시간 복잡도가 O(n^2)이 나와서

효율성 테스트를 통과하지 못하고 헤맸다.

위 풀이는 다른 사람들의 풀이를 참고한 것인데 시간 복잡도도 O(n)이고 코드도 매우 간결하다.

 

핵심은 차들을 나간 순서대로 정렬하는 것이다.

그로 인해서 모든 경우를 체크하지 않고 카메라를 기준점으로 체크하면서

반드시 필요한 지점에 추가로 카메라를 배치하면 된다.

 

내가 푼 방법은 완전 탐색에 가깝고 이 풀이가 진정한 Greedy 접근 방식이라 생각하여 소개해봤다.

뭔가 알고리즘에 있어서 아직 갈길이 멀다고 생각이 든 문제이다.