[프로그래머스] 단속카메라 - 그리디(greedy) (python)

1. 문제 설명

 

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

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

 

---

2. 제한 사항

 

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

---

3. 입출력 예

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

 

---

4. 나의 풀이

이 문제는 프로그래머스 스킬 체크 3단계를 풀 때 두번째로 나왔던 문제였다. 종이에 수직선을 그리고 공통 부분을 어떤식으로 생각하면 좋을지 접근하니 쉽게 문제가 풀렸다.

 

def solution(routes):
    routes.sort()
    answer = 0
    temp = routes[0]
    for i in routes[1:]:
        if temp[1] < i[0]:
            answer += 1
            temp = i
        else:
            temp = [i[0], min(temp[1], i[1])]

    return answer + 1

 

경로가 담긴 리스트를 시작점을 기준으로 정렬하고, 순서대로 비교하며 단속용 카메라를 설치할 수 있는 구간을 저장하면서 공통 구간이 없으면 answer에 +1 하는 방식으로 반복문을 돌렸다.

그리디를 여러개 풀면서 느낀건데, 문제를 읽고 실제 예시를 직접 생각해서 해결하려고 하다 보면 알고리즘을 구상할 수 있게 된다. 이런 부분에서 다른 알고리즘들 보다 접근하기 쉽다고 생각했다. 오하려 요즘 DP가 너무 어려워서 문제를 많이 풀어봐야 겠다고 생각했다,,,,,,

 

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42884

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