파트7. 탐욕법 - [Greedy] 실습문제3 (단속카메라 42884번) python

def solution(routes):
    answer = 0
    q = 10
    routes.sort(key=lambda x: x[0], reverse=True)
    for i in routes:
        if q>=i[0]:
            if i[0]<=q<=i[1]:
                continue
            q=i[0]
            answer+=1
    return answer

1트만에 정답이라고 떠서 매우 좋아하고 있었다.

그리고 gpt한테 코드 어떤지 물어봤는데 ...

구리다는 팩폭을 당해 코드를 구글링과 함께 수정해보았다.

 

gpt의 피드백

• 비효율적인 정렬 기준 - 진입지점이 아니라 진출 지점을 기준으로 정렬하기
  • 차량의 경로가 겹치는 부분을 정확히 판단하려면 차량이 고속도로를 떠나는 지점을 기준으로 카메라를 배치하는 것이 합리적이다.
• 조건문의 복잡성
  • if i[0] <= q <= i[1]로 단속 여부를 판단하지만, 이 조건은 이미 단속된 차량을 다시 검사하고 있기 때문에 비효율적이다.

gpt의 코드

def solution(routes):
    routes.sort(key=lambda x: x[1])  # 진출 지점 기준 정렬
    cameras = 0
    current_camera = -30001  # 카메라의 초기 위치 (가능한 최소값)

    for route in routes:
        # 현재 카메라가 해당 차량을 단속하지 못한다면
        if current_camera < route[0]:
            cameras += 1
            current_camera = route[1]  # 새로운 카메라 설치

    return cameras

 

아래는 구글링을 통해 찾은 코드이다.

def solution(routes):
    routes.sort(key = lambda x : x[1])
    answer = 1
    prev_end = routes[0][1]
    for start, end in routes :
        if start > prev_end :
            answer += 1
            prev_end = end

    return answer