[파이썬] 단속카메라

문제 설명

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

 

제한사항

• 차량의 대수는 1대 이상 10,000대 이하입니다.
• routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
• 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

입출력 예

routes	return
[[-20,-15], [-14,-5], [-18,-13], [-5,-3]]	2

 

입출력 예 설명

-5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.

-15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.

 

 

💕 나의 풀이

def solution(routes):
    answer=0
    pos=-30001
    routes.sort(key=lambda x : x[1])
    while routes :
        i, o=routes.pop(0)    # 진입, 진출
        if pos < i :
            pos=o
            answer += 1
    return answer

진출 지점이 작은 순서대로 정렬한다.

현재 카메라가 설치된 pos보다 진입 지점이 더 크면 새로운 진출 지점 o에 카메라를 설치

 

 

🎀 다른사람 풀이

# 출처 : https://wwlee94.github.io/category/algorithm/greedy/speed-enforcement-camera/
def solution(routes):
    answer=0
    # 진출을 기준으로 오름차순
    routes.sort(key=lambda x: x[1]) 
    camera=-30001
    
    for route in routes :
        if camera < route[0] :
            answer+=1
            camera=route[1]
    return answer

카메라 설치 위치가 차 진입 지점 route[0]보다 작으면 answer을 1 늘린다. 현재 지점에 카메라 설치해야함.

camera를 진출 지점 route[1]로 갱신하고 반복문을 계속 진행한다.

 

 

# 출처 : https://velog.io/@tjdud0123/%EB%8B%A8%EC%86%8D-%EC%B9%B4%EB%A9%94%EB%9D%BC
def solution(routes):
    ENTER, EXIT, N=0, 1, len(routes)
    routes=sorted(routes, key=lambda x:x[1])
    check=[False]*N
    camera, count=-30000, 0
    for i in range(N) :
        if check[i] :
            continue
        count+=1	# 카메라 설치
        camera=routes[i][EXIT]	# 진출지점
        for i in range(i, N) :	# 다른 차 검사
            if routes[i][ENTER] <= camera and camera <= routes[i][EXIT]:
                check[i]=True
    return count

routes를 진출지점을 기준으로 오름차순 정렬

차를 검사했는지 확인하기 위해 check 리스트를 만든다.

진입 지점이 camera보다 같거나 작고, 진출 지점이 camera보다 크거나 같으면 check에 True를 넣는다.

 

 

# 출처 : https://velog.io/@coding_egg/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%8B%A8%EC%86%8D%EC%B9%B4%EB%A9%94%EB%9D%BC-python-%ED%8C%8C%EC%9D%B4%EC%8D%AC
from sys import maxsize

def solution(routes):
    routes.sort(key=lambda x:(x[0], x[1]))
    m=-maxsize
    M=maxsize
    cnt=0
    
    for s, e in routes :    # 진입, 진출
        if M < s :
            cnt+=1
            m=s
            M=e
        else:
            if m < s :
                m=s
            if M > e :
                M=e
    cnt+=1
    return cnt

 

 

 

💁‍♀️ 출처 : 프로그래머스