[Python][Greedy?] 단속카메라 - 프로그래머스 Lv.3

[문제]

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

프로그래머스

 

[알고리즘]

• routes를 진출 지점를 기준으로 정렬한다.
• 첫번째 차의 진출 지점을 camera를 설치한다.
• 두번째 차부터 다음을 반복한다.
  • 마지막 camera 설치 지점보다 i번째 차의 진입 지점이 작다면, continue
  • 그렇지 않다면 그 차의 진출 지점을 위치로 카메라 설치.
• 설치된 카메라 개수 출력

[느낀점]

• 처음엔 진입 지점을 기준으로 정렬하였는데, 실행결과는 통과하였지만, test case 모두 실패.
• 진입 지점을 기준으로 정렬할 시 예외 케이스 발견. 

[코드]

def solution(routes):
    answer = 0
    routes_sorted = sorted(routes, key=lambda x:x[1])
    
    cam_loc = [routes_sorted[0][1]]
    for i, (start, end) in enumerate(routes_sorted[1:]):
        if start <= cam_loc[-1] : 
            continue
        
        cam_loc.append(end)
    answer = len(cam_loc)
    
    return answer

정확성 테스트

테스트 1 〉	통과 (0.02ms, 10.3MB)
테스트 2 〉	통과 (0.04ms, 10.1MB)
테스트 3 〉	통과 (0.04ms, 10.2MB)
테스트 4 〉	통과 (0.04ms, 10.2MB)
테스트 5 〉	통과 (0.04ms, 10.1MB)

효율성 테스트

테스트 1 〉	통과 (0.45ms, 10.5MB)
테스트 2 〉	통과 (0.28ms, 10.4MB)
테스트 3 〉	통과 (0.95ms, 10.6MB)
테스트 4 〉	통과 (0.04ms, 10.2MB)
테스트 5 〉	통과 (1.11ms, 10.7MB)