고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.
고속도로를 이동하는 차량의 경로 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 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.
https://programmers.co.kr/learn/courses/30/lessons/42884?language=python3
- Tool: Visual Studio Code
- SDK: Python 3.7.2
- Language: Python
python Problem.py- Open folder "42884" by Visual Studio Code
- Check out settings - launch.json
- Press F5 to debug start
- 우선 문제를 풀기 전에 오류를 잡아야 한다.
- 입출력 예 설명대로라면 -15, -5 지점에 카메라가 설치되어야 하는데
- 이게 맞으려면 첫번째 array value인 [-20, 15]가 [-20, -15]여야 된다.
- 아니면 예제 입력대로 해서 답을 맞추면 역시 답이 2로 같지만 예제 설명이 달라야 한다.
- -13 지점에 카메라를 설치하면 첫 번째, 두 번째, 세번째 차량이 카메라를 만나고
- -3 지점에 카메라를 설치하면 네 번째 차량이 카메라를 만나게 되어 있다.
- 프로그래머스야 이거 언제 고칠거냐?
- 가장 작은 값을 가진 진출로 순서대로 sort를 걸어 놓고
- 나갈 때 마다 그 값보다 작은 진입로를 가진 차들을 모두 찾아내서 단속 카메라에 걸릴 수 있게 만든다. 단속 카메라에 걸릴 수 있는 차는 array에서 삭제하는 것으로 판단해 본다.
- 이제 남은 차들 중에 그 다음 큰 값을 가진 진출로 보다 작은 값의 진입로를 가진 차들을 모두 찾아내면 단속 카메라에 걸린다.
- 이런 식으로 계속 찾아내면 최소한의 단속 카메라로 모든 차들을 단속할 수 있다.
두 가지 이유를 생각해 볼 수 있는데
- 어차피 최초로 진출하는 차부터 최소 한대의 단속카메라가 필요하다. => 어쩔 수 없고도 당연한 얘기
- 진출하는 차 기준으로 진출로 값보다 작은 값으로 진입한 차는 모두 단속할 수 있으므로 진출로 ascending order 기준으로 단속을 해 나가면 쉽게 풀리기 때문이다.
- 일단 진출로 값이 작은 기준으로 sort를 걸면 다음과 같이 된다.
- [[-18,-13], [-14,-5], [-5,-3], [-20,15]]
- 첫 차인 0번차가 나가는 진출로에 카메라를 설치하면 그 다음 이후 차들 중에 진출로 보다 작은 진입로의 값을 가지는 차들(들어온 차들)은 모두 단속이 가능 하게 된다. = -13 지점 => sorted routes 기준으로 1번 3번차가 걸리므로 단속이 됐다고 보고 routes list에서 삭제
- 그 이후 첫 차에서 나가는 시점의 진출로 보다 큰 차가 등장(2번차)하면 그 차가 나가는 시점의 진출로(-3지점)에 또 카메라를 설치하는 식으로 하면 최소 단속 카메라 설치가 가능해진다. => 나머지 한대가 나가는 시점에 카메라 설치 = -3 지점
- 마지막 차의 진출로에 카메라 설치하고 나갔으므로 총 2대 설치하고 끝남
- 엑셀로 그려본 설명 링크
- https://docs.google.com/spreadsheets/d/1prpwf15Wq-XRPPJIrXmMehYHZG8kDZixGQVyE_vSLEE/edit?usp=sharing
- 탐욕법은 사실 문제만 잘 이해하면 쉽게 풀리는 것 같다. 어려운 알고리즘은 아니다.
- 상식적으로 생각하는 방식이라면 풀리는 편이고 이걸 코드로 옮기는 과정이 올바르면 탐욕법이 사실 제일 쉬운 전략인 듯 하다.