문제
접근
진입 지점 혹은 진출 지점 중 하나를 기준으로 놓고 문제를 풀면된다.
나는 진입 지점을 기준으로 잡고 진입 지점으로 정렬해주었다.
가장 늦게 진입한 차의 진입점에 카메라를 설치하고, 해당 카메라와 만나는 차들을 모두 제거한다.
남는 차중 가장 늦게 진입한 차의 진입점에 또 카메라를 설치하고, 차가 안남을 때까지 반복해주면 된다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def solution(routes):
answer = 0
routes.sort(key = lambda x:-x[0])
print(routes)
while routes:
x = routes[0][0]
answer+=1
tmp = []
for route in routes:
if route[0] <= x and x <= route[1]:
continue
else:
tmp.append(route)
routes = tmp
return answer