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

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

프로그래머스

---

• 풀이1
  • 진출지점에 카메라를 설치해야 최소로 설치가 가능하다
  • 그러므로 진출지점을 기준으로 정렬
  • 진출지점에 설치하고 난 후 이 카메라와 만나는 차량은 pass / 만나지 않는 차량의 진출시점에 카메라 설치
  • 반복
• 코드1

def solution(routes):
    # 나가는 지점 오름차순으로 정렬
    routes.sort(key=lambda x:x[1])
    # 카메라 개수
    answer = 0
    # 차량 경로 번호
    idx = 0
    while idx < len(routes):
    	# routes[idx]의 진출 지점에 카메라 설치
        t = routes[idx][1]
        answer += 1
        # 위 카메라를 만나는지 확인
        for i in range(idx+1,len(routes)):
        	# 위 카메라와 만난다면 다음 카메라는 다음 차량에
            if routes[i][0] <= t <= routes[i][1]:
                idx += 1
            # 만나지 않는다면 이 차량 진출 지점에 카메라 설치해야함
            else:
                break
        idx += 1
    return answer

• 풀이2
  • 카메라가 지금 차의 진입지점보다 전이라면 이 차의 진출지점에 카메라 설치
  • 반복
• 코드2

def solution(routes):
    # 나가는 지점 오름차순으로 정렬
    routes.sort(key=lambda x:x[1])
    # 카메라 개수
    answer = 0
    # 카메라 위치
    camera = -30001
    for start,end in routes:
        # 카메라가 진입시점보다 전이라면 카메라 하나 추가
        if camera < start:
            answer += 1
            # 카메라를 진출 시점에 추가
            camera = end
    return answer