문제 링크
문제 요약
그리디 유형 에 해당한다.문제에서의 조건은 다음과 같다.
1 ) 모든 차량이 고속도로를 이용하면, 카메라를 무조건 한 번은 만나도록 설치하는 것이 목표
2 ) 최소 몇 대의 카메라를 설치해야하는지!
처음에는 단순하게 수직선으로 그려서 생각해보았는데, 구간이 겹치는 부분은 cctv가 중복되어서 설치될 필요가 없고, 겹치지 않는 부분 (즉, 허점이 될 수 있는 곳)에 cctv를 설치해주어야한다.
따라서, 차량이 나가는 시점을 기준으로 오름차순 정렬을 진행해주고 단순하게 앞의 차량이 나간 시점과 그 다음 차량의 진입 시점이 겹치는 지 여부를 판단해주면 되는 문제이다.
문제 풀이
def solution(routes):
cctv = 1
# Routes : 차량 진입, 차량 나간 시점
routes.sort(key = lambda x:x[1]) # 나간시점을 기준으로 정렬
_in, _out = routes[0][0], routes[0][1]
for i in range(1, len(routes)):
s, e = routes[i][0], routes[i][1]
#print(s, e, _out)
if s > _out:
# 하나 뒤 진입 지점이 앞 차의 나가는 시점보다 크면, 공백이 생기니까 cctv 추가
cctv+=1
#print(cctv)
_out = e
return cctv
📌 느낀 점
- 한 번 로직을 생각하면 정말 금방 구현이 되는 문제이지만, 빠르게 생각해내기 조금 힘들었던 것 같다.
