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

🔗 출처

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

✅ 아이디어

1. 정렬
2. 기준점을 다르게 생각해보기

✅ 코드

def solution(routes):
    routes.sort(key=lambda x: x[1])
    key = -30001 # 카메라 위치
    cnt = 0 # 카메라 수
    for route in routes:
        if route[0] > key: # 기준(카메라)보다 진입지점이 뒤에 있으면
            cnt += 1 # 카메라 설치 증가
            key = route[1] # 나간 지점을 기준으로 설정
    return cnt

참고 코드 : https://velog.io/@jqdjhy/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%8B%A8%EC%86%8D%EC%B9%B4%EB%A9%94%EB%9D%BC-Greedy

🔥 배운것

풀지못했다.

정렬까지는 했지만 그 이후 어떻게 풀어가야할 지 생각이 나지 않았다.
생각해보면 왜 정렬을 한지도 스스로에게 명확한 설명을 할 수 없었다.

나의 생각방향?
예제를 보고 힌트를 얻음

1. 최대한 겹치는 구간에 설치하면되지 않을까? -> 겹치는 구간 찾기
   [[-20,-15], [-14,-5], [-18,-13], [-5,-3]]
2. 겹치는 구간을 어떻게 찾을까? 첫 경로 -> 나머지 경로와 모두 비교 겹치는 것 찾기? -> 시간복잡도가 올라간다. 왜? 하나하나 모두 비교해야하기 때문

해답에서는 2번의 문제를 해결하기위해 경로별 진입기준을 기준으로 오름차순 정렬한다. 또 정확히 어떤 지점(위치)에 카메라를 놓는 다는 것이 아니라 범위를 기준으로 기준(key)을 바꿔가면서 해결함.

부족한것

1. 생각한 것을 코드로 옮기는 구현력(실험 포함)
2. 문제에서 요구하고자 하는 것들만 구하자(왜 굳이 개수로 주었을까?)