[Programmers] Level 3. 단속 카메라

🔗 Problem Link

프로그래머스

---

❔Thinking

• 차량의 진입,진출 기록이 각각 담긴 routes를 활용해, 모든 차량을 단속할 수 있는 최소 카메라 개수를 반환한다.
• 진입과 진출 시에 만나는 단속카메라도 단속이 가능하다.

---

💻Solution

1. 뒤에서부터 차례로 확인해나가는 풀이

def solution(routes):
    answer = 0
    routes = sorted(routes, key=lambda x: x[0])
    while routes:
        camera_site = routes.pop()[0] # 카메라 설치
        while routes:
            start, end = routes[-1]
            if end >= camera_site: # 현재 카메라 위치로 단속이 가능할 경우
                routes.pop()
            else: # 새로운 카메라 설치가 필요한 경우
                break
        answer += 1
    return answer

 

2. 앞에서부터 차례로 확인해나가는 풀이

def solution(routes):
    routes = sorted(routes, key=lambda x: x[0])
    camera_site = -30001 # 최초 카메라 위치 설정
    answer = 0
    for route in routes:
        if camera_site < route[0]: # 현재 카메라 위치로 단속이 불가능한 경우
            answer += 1
            camera_site = route[1]
    return answer

---

🗝️keypoint

1. 차량의 진입부터 진출 전까지, 단 한번만 단속카메라를 지나면 단속이 가능하다.
2. 새롭게 확인하는 차량의 진입 진출 사이에 단속카메라가 있다면, 설치 없이 다음 차량의 정보를 확인한다.