[프로그래머스] 단속카메라

문제

• 고속도로를 이용하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 한다. 
• 고속도로를 이동하는 차량의 경로 routes 가 매개변수로 주어질 때, 최소 몇 대의 카메라를 설치해야 하는지 리턴하기
  • 차량 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난 것으로 간주한다.
• 1 <= 차량 대수 <= 10,000
• -30,000 <= 차량 진입 지점, 진출 지점 <= 30,000

 

풀이

• 정렬한 다음 필요한 경로에 하나씩 설치한다.
  • 첫 번째 차량의 진출 지점에 카메라를 설치했다고 가정했을 때, 그 다음 차량의 진입 지점이 이전 차량의 진출 지점과 겹치지 않는다면 추가로 카메라 설치가 필요하다.

 

def solution(routes):
    routes.sort()
    answer = 1              # 첫 번째 차의 진출 지점에 설치
    camera = routes[0][1]   # 현재 카메라의 위치
    for s, e in routes :
        # 현재 차량의 진입 시점이 이전 카메라 위치보다 앞설 때 
        # 현재 차량의 진출 시점에 카메라 새로 설치
        if s > camera :
            answer += 1
            camera = e
        # 카메라 위치를 이전 차량의 진출 시점과 현재 차량의 진입 시점 중 더 앞선 지점으로 변경
        else :
            camera = min(camera, e)
    return answer

 

References

• 프로그래머스 고득점Kit 그리디