문제 소개
고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.
고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.
[[-20,15], [-14,-5], [-18,-13], [-5,-3]] return 2시나리오
카메라를 설치할 때, 각 지점마다 차량이 몇 대 지나가는 지 계산하기에는 다음의 제약 조건 때문에 비효율적이였다.
차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.
먼저, 진입 지점이 아닌 진출 지점을 기준으로 정렬했다.
[[-18, -13], [-14, -5], [-5, -3], [-20, 15]]리스트를 왼쪽부터 하나씩 꺼내면서 설치된 해당 경로에 설치된 카메라가 없다면 진출 지점을 새로운 카메라로 설치해주었다.
여기서, 진출 지점을 기준으로 한 이유는 진출 지점을 기준으로 정렬 하면서 완전 탐색을 하지 않고 가장 깊숙한 지점에 설치하여 겹치는 부분을 최대한 만들고자 하였기 때문이다. 그리디하게~
카메라는 -13 지점에 먼저 설치되고 다음으로 -3 지점에 설치되며 routes가 비어지게 된다.
문제 설명의 예시와는 다르더라도 정확도, 효율성을 모두 성공했다.
def solution(routes):
answer = 0
routes.sort(key=lambda x:x[1])
cameras = set()
while routes:
start, end = routes.pop(0)
checking = False
for camera in cameras:
if start <= camera <= end:
checking = True
break
if not checking:
cameras.add(end)
answer += 1
return answer풀이 후 다른 사람들의 풀이를 보며 보완할 점을 찾았다. 나의 풀이는 set에 저장 후에 set에 들어간 모든 지점을 체크하는데, 만약 set이 커질 수록 효율성은 저하될 것이다.
하지만, 다음과 같은 풀이는 하나의 카메라만 저장하여 효율성을 높였다.
마지막 카메라만 저장함으로서 가장 깊숙한 지점에 카메라가 설치된다. 진출 지점을 기준으로 정렬한 후에 탐색했기 때문에 이후의 자동차들의 진출 지점은 적어도 카메라보다 같거나 후에 있다. 결국, 이전의 카메라의 지점을 모두 기억하지 않아도 확인할 수 있다.
문제 풀이
def solution(routes):
routes = sorted(routes, key=lambda x: x[1])
last_camera = -30000
answer = 0
for route in routes:
if last_camera < route[0]:
answer += 1
last_camera = route[1]
return answer