728x90
문제 요약
고속도로를 이동하는 차량의 경로 routes 가 매개변수,
모든 차량이 한번은 단속용 카메라를 만나려면 최소 몇 대의 카메라 설치해야하는지 return
차량의 대수는 1대 이상 10,000대 이하
routes에는 차량의 이동 경로 포함, routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점,
routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점
진입/진출 지점에서도 카메라를 만난 것
return
| routes | return |
| [[-20,-15], [-14,-5], [-18,-13], [-5,-3]] | 2 |
return
- 5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.
- 15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.
나의 풀이 (정답)
def solution(routes):
sorted_data = sorted(routes, key=lambda x: x[0])
answer = 0
target = sorted_data[0]
for i in range(1, len(sorted_data)):
if target[1] >= sorted_data[i][0]:
target[0] = max(target[0], sorted_data[i][0])
target[1] = min(target[1], sorted_data[i][1])
if i == len(sorted_data) -1: # 겹칠 때, 마지막
answer += 1
else:
target = sorted_data[i] # 타겟 초기화
if i == len(sorted_data) -1: # 안 겹칠 때, 마지막
answer += 1
answer += 1
return answer
수직선 위에 선을 긋는 것과 같다.
여러 개가 겹치는 경우를 찾기 위해 target 을 설정하였다.
728x90
