[프로그래머스] LEVEL3 단속카메라 (Python)

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

---

🧐 문제 설명

---

😍 나의 풀이

카메라의 수를 최소로 하려면, 경로가 최대한 많이 중첩이 되는 지점에 카메라를 설치해야한다.

Greedy로 풀기 위해서 카메라의 설치는 진입 혹은 진출 지점에 설치하는 것으로 고려한다. 그래야 가장 적은 카메라를 설치할 수 있다.

1. 순차적으로 탐색하여 탐욕법을 쉽게 하기 위해서 진출 지점을 기준으로 routes를 정렬해준다. 그리고 카메라의 위치를 변수로 정한다.(위 문제에서는 카메라의 범위가 -30000~+30000이기 때문에 default를 -30001로 설정)

2. 카메라의 위치가 진입 시점보다 작다면
   → 그 경로를 카메라가 검사하지 못한다는 의미
   
   위 그림과 같이 카메라의 위치가 진입 시점보다 작은 경우 카메라는 해당 차량의 경로를 검사할 수 없다. 그러므로 이 경로를 검사하기 위해서 위 경로의 진입시점 ~ 진출시점에 설치해야한다.

3. 카메라의 위치를 진출 시점에 설치해야 Greedy한 방식
   

※ 진출 시점을 기준으로 미리 정렬을 해놓았기 때문에 카메라를 진출 시점에 설치하면 모든 경우를 체크할 수 있다.

예시로, 정렬이 안 되어있다면 위의 사진처럼, 파란색 경로는 첫번째 카메라가 체크할 수 없는 경우가 발생한다. 하지만 진출 시점으로 정렬하기 때문에 위의 예시는 다음과 같이 바뀌므로 로직에 부합하게 된다.

def solution(routes):
    answer = 0
    last_camera = -30001
    routes = sorted(routes, key = lambda x:(x[1]))
    
    for i in routes:
        if last_camera < i[0]: # 가장 마지막 위치에 설치한 카메라가 차량의 진입시점에 없다면
            answer += 1 # 그 경로는 감시하지 못하므로 카메라 새로 설치
            last_camera = i[1] # 카메라의 위치는 진출시점에 설치(greedy하게)
    
    return answer

---

👏 다른 사람의 풀이

def solution(routes):
    routes.sort()
    length=len(routes)
    count=0
    cam=[0]*length
    camera=0
    for i in range(length-1,-1,-1):
        if cam[i]==0:
            camera=routes[i][0]#진입 지점
            count+=1
        for j in range(i,-1,-1):
            if cam[j]==0 and routes[j][1]>=camera:#이전 진입점(camera)이 현재 진출점보다 작거나 같다면 카메라 설치
                cam[j]=1 #카메라가 구간을 커버함
    return count

---

🥇 Today I Learn

greedy 알고리즘은 그 때 그 때 최선의 선택을 해야하므로 값이면 값을 기준으로 경로면 경로를 기준으로 정렬을 하고 푸는 것이 정석적인 풀이!!