211124 - 단속 카메라

◾ 단속카메라 : 프로그래머스 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

---

◾ 풀이

1. 해설

• routes를 정렬하여 시작 지점을 기준으로 필요한 카메라의 수를 계산한다.
• 예시) [-20,-15], [-14,-5] => [-14, -5], [-20, -15]
  • 카메라 위치와 차량의 끝 지점과 비교
  • 카메라 위치 -14로 초기화
  • 카메라 : -14, [-14, -5] 가능
  • 카메라 : -14, [-20, -15] 불가능
  • 카메라 : -20, [-20, -15] 가능
  • 총 2개 필요

---

2. 프로그램

1. 출발 지점을 기준으로 내림차순 정렬
2. 카메라의 위치를 첫 차량의 출발 지점으로 설정
3. 다음 차량의 도착 지점과 비교
   • 도착 지점이 카메라 위치 이상인 경우 카메라는 만나는 것
   • 아닌경우 카메라 새로 설치

# 코드
def solution(routes):
    answer = 1

    routes.sort(key=lambda x : (-x[0]))
    print(routes)

    camera = routes[0][0]
    for start, end in routes[1:]:
        if end >= camera:
            continue
        else:
            camera = start
            answer += 1

    return answer