( 문제 설명 )
고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.
고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.
제한사항
- 차량의 대수는 1대 이상 10,000대 이하입니다.
- routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
- 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
- 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.
입출력 예
routesreturn| [[-20,-15], [-14,-5], [-18,-13], [-5,-3]] | 2 |
입출력 예 설명
-5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.
-15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.
( 문제 해설 )
1. routes를 정렬한다 + routhes 길이만큼 감시카메라 설치 여부 체크용 리스트 생성 chk [4]
2. routes 길이만큼 순회 시작 ( length라고 하겠다 ) # i = 0 ~ length
3 chk [i] == 0 이면 감시카메라를 설치할 거임 ans+= 1
3-1. 그리고 설치했으니까 똑같은 곳에는 설치할 필요가 없으니 chk [i] = 1이라고 변경
3-1. 카메라는 해당 고속도로의 마지막 부분에 설치할 거고 그 부분을 표기 camera = routes [i][1]
4. i + 1부터 lengtg 만큼 for문안에서 다시 순회 # j = i + 1 ~ length
4-1. 그다음 고속도로가 설치된 카메라 사이에 있다면 chk [j] = 1로 표기 ( 중첩되게 설치하지 않기를 문제에서 원하기 때문에)
5. i 가 length만큼 도달? no = 아니라면 다시 2번으로 반복. yes = 종료
[ 코드 ]
# 6. 단속 카메라
def solution(routes):
answer = 0
routes.sort(key=lambda x: x[1])
print(routes)
length = len(routes)
chk = [0] * length
for i in range(length):
if chk[i] == 0: # 설치해야되면 카메라 갱신
camera = routes[i][1] # 나가는 지점에 카메라를 갱신
answer += 1
for j in range(i + 1, length):
if routes[j][0] <= camera <= routes[j][1] and chk[j] == 0: # 설치 안해도 되는 지점 chk
chk[j] = 1
return answer후기
chk를 둬서 구간 하나하나 라를 체크하지 않게끔 한 게 좋다.
그림과 글과 알고리즘 상황이 조금 다르다
그림은 이중 포문 안에 포문을 생략했다
하지만 그림을 이해했다면 글도 코드도 이해가 잘 가실 것.