프로그래머스 Lv.3 | Python | 단속카메라

1. 문제 정보

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

프로그래머스

 

난이도: Lv.3

---

2. 문제 설명

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

제한사항

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

---

3. 접근 기준

이 문제의 핵심은 “모든 구간을 최소 개수의 점으로 커버”하는 것이다.

따라서 다음 기준으로 접근한다.

• 차량 경로는 구간(interval)이다.
• 하나의 카메라는 여러 차량을 동시에 커버할 수 있다.
• 가능한 한 많은 구간을 한 번에 커버하는 위치에 설치해야 한다.

→ 구간을 기준으로 최소 지점 선택 문제 (Greedy)

---

4. 사용한 패턴 / 알고리즘

그리디 (Greedy)

• 기준: 진출 지점 기준 정렬
• 가장 빨리 끝나는 구간부터 처리
• 현재 카메라로 커버 가능한지 판단

이 문제는 “최소 개수로 구간 커버” 유형의 대표적인 그리디 문제다.

---

5. 핵심 아이디어

카메라는 진출 지점(end)에 설치하는 것이 최적이다.

이유:

• 가장 먼저 끝나는 차량 기준으로 카메라를 설치하면
• 그 지점을 지나가는 다른 차량들도 최대한 많이 커버할 수 있다.

동작 방식:

1. routes를 진출 지점 기준으로 정렬
2. 첫 번째 차량의 진출 지점에 카메라 설치
3. 다음 차량을 보면서:
   • 현재 카메라 위치보다 시작점이 뒤라면 → 새 카메라 필요
   • 아니면 → 기존 카메라로 커버 가능

---

6. 풀이 코드

def solution(routes):
    routes.sort(key=lambda x: x[1])  # 진출 지점 기준 정렬
    
    camera = -30001
    answer = 0
    
    for start, end in routes:
        if start > camera:
            answer += 1
            camera = end
    
    return answer

---

7. 동작 흐름 예시

예:

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

정렬 후:

[-20, -15]
[-18, -13]
[-14, -5]
[-5, -3]

진행:

카메라 위치 = -15 (첫 차량 기준)

[-18, -13] → -15 포함됨 → 커버됨
[-14, -5] → -15보다 시작이 뒤 → 새 카메라 필요 → -5 설치
[-5, -3] → -5 포함됨 → 커버됨

결과: 카메라 2개

---

8. 핵심 로직 요약

이 문제의 핵심은 구간을 끝나는 지점 기준으로 정렬한 뒤, 최소 개수의 지점으로 모든 구간을 커버하는 것이다.

• 차량 경로를 진출 지점 기준으로 정렬한다.
• 가장 먼저 끝나는 구간의 끝 지점에 카메라를 설치한다.
• 이후 구간을 순회하면서:
  • 현재 카메라 위치보다 시작점이 뒤라면 새로운 카메라를 설치한다.
  • 그렇지 않으면 기존 카메라로 커버한다.

“진출 지점 기준 정렬 + 겹치는 구간 최대 활용 + 필요할 때만 카메라 추가”
이 세 가지가 핵심이다.

---

9. 정리

이 문제는 단순히 겹치는 구간을 찾는 문제가 아니다.
핵심은 어디에 설치해야 가장 효율적으로 커버할 수 있는가다.

• 구간 문제 → 끝나는 지점 기준 정렬
• 최소 개수 → 그리디 선택
• 겹침 여부 → 시작점과 현재 카메라 위치 비교

→ “구간 + 최소 개수”가 나오면 그리디를 먼저 의심해야 한다.