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

 

📌문제

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

 

🎖️난이도

Level 3

 

✔️풀이

def solution(routes):
    routes.sort(key = lambda x : x[1]) # 빠져나간 시간 기준으로 오름차순 정렬
    camera = routes[0][1] # 첫번째 차 빠져나간 곳("진출 기준")에 우선 첫번째 카메라 설치하고 시작
    cnt = 1
    
    for i in range(1, len(routes)):
        if routes[i][0] > camera: # 진입 시점이 기존 카메라 위치보다 더 밖(앞)에 있으면
            cnt += 1
            camera = routes[i][1] # 진출 시점에 새로 설치
            
    
    return cnt

 

🧠노트

그리디..

애초에 "늘 최적의 답이 되는 알고리즘이 아님"을 기억하고

"각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길" 바라며 좁은 시선으로 생각하고 질러버리자!

 

즉, 

"전체적으로 봤을 때도 이게 진짜 최적(최소, 최대)일까?" 라고 생각하면서 머뭇거리지 말고

일단 기본적인 한 단계에서, 나만의 기준을 하나 잡고, 알고리즘을 세워보자!!

 

이 문제 같은 경우에도

진출 지점(빠져나간 곳)을 기준으로 잡고,

정렬 후 첫번째 차량의 진출 지점(-15)에 우선 첫번째 cctv를 설치한다.

그 다음 계속 한 차량씩 cctv 위치 & 진입 지점(들어온 곳)을 비교하면서 설치 or not을 결정해주면 된다.

 

그리디는 솔직히 처음에 아이디어가 안떠오르면 계속 안풀려서,,

경험을 많이 쌓자!

 

🔍참고

-