https://school.programmers.co.kr/learn/courses/30/lessons/42884
접근 방법
차량의 진출 순서를 기준으로 정렬하고, 앞에서부터 카메라를 설치해간다.
그리디 알고리즘을 활용할 수 있다.
- 예시에서 카메라는 다음과 같이 설치될 수 있다. 하지만 최대한 많은 차가 겹치도록 하기 위해서는 중간 보다는 진출 또는 진입시점에 설치하는게 좋다.
- 풀이에서는 진출 시점에 카메라를 설치했다.
- 자동차의 진출 시점에 카메라를 설치하는 과정을 살펴보면 다음과 같다.
풀이
def solution(routes):
routes.sort(key = lambda x: x[1]) # 진출 시점을 기준으로 정렬한다.
camera = routes[0][1] # 가장 첫번째 차량의 진출 시점을 카메라 한개로 설정
answer = 1
for i in range(1, len(routes)):
if routes[i][0] > camera:
camera = routes[i][1] # 현재 진출 시점에 카메라를 추가한다.
answer += 1
return answer
정리
- 그리디 알고리즘임을 알아도 풀지 못했다.
- 그리디 알고리즘: 현재 상황에서 지금 당장 좋은 것만 고르는 방법
- 그 아이디어를 떠올리기가 힘든 것 같다.
Uploaded by N2T
