프로그래머스 단속 카메라 (파이썬)

Level 3, Greedy

 

문제 : https://programmers.co.kr/learn/courses/30/lessons/42884?language=python3 

코딩테스트 연습 - 단속카메라

 

1. 나간 기준 오름차순 정렬

2. 카메라 위치 -30001로 초기화

3. if 나간 지점 >= 다음 차량 진입 지점 ( 두 차량이 겹치는 경우)
       continue (다음 차량 확인) 

   else:

       차량 나간 지점에 마지막 카메라 위치 초기화

       answer += 1

 

제출 코드

def solution(routes):
    answer = 0
    routes.sort(key = lambda x : x[1])
    lastCameraPosition = -30001
    for IN, OUT in routes:
        if lastCameraPosition >= IN:
            continue
        else:
            lastCameraPosition = OUT
            answer += 1
    return answer

 

결과 및 정리 

그리디를 이용해야하지만 어떻게 정렬을 하고 무엇을 우선으로 선택해야하는지 감이 오지 않았습니다.

제가 정한 제한 시간안에 풀리지 않고 고민하면 할수록 복잡해지기만 하고 답이랑 멀어지는 것 같아 빠르게 검색의 도움을 받았습니다.

 

다음 차량의 진입시간이 이전 차량의 진입시간보다 이상인지 미만인지로 구분하는 것으로 해결했습니다.