전기차 최근접 충전 스테이션

문제

한 고속도로 운영사가 전기차 내비게이션에 들어갈 "가까운 충전소 안내" 기능을 만들고 있습니다.

고속도로는 하나의 직선이고, 각 지점은 기점으로부터의 거리(m)인 정수 좌표로 표현됩니다. 충전 스테이션의 좌표 목록 stations는 오름차순으로 정렬되어 있고 서로 다른 값입니다. 같은 길이의 배열 available은 각 스테이션의 상태로, available[i]가 true면 i번 스테이션은 이용 가능하고 false면 점검 중이라 이용할 수 없습니다.

주행 중인 차량들의 좌표 목록 cars가 주어집니다. 각 차량마다 이용 가능한 스테이션 중 거리(좌표 차이의 절댓값)가 가장 가까운 스테이션의 좌표를 안내해야 합니다.

• 가장 가까운 스테이션이 두 곳이면(양쪽 거리가 같으면) 좌표가 더 작은 쪽을 안내합니다.
• 차량이 스테이션과 같은 좌표에 있으면 거리는 0이며 그 스테이션을 안내합니다.
• 이용 가능한 스테이션이 하나도 없으면 그 차량에는 -1을 안내합니다.

cars의 순서대로 안내할 좌표를 담은 배열을 반환하는 solution(stations, available, cars) 함수를 작성하세요.

예시

예시 1 설명:

• 차량 0: 왼쪽에 스테이션이 없으므로 가장 왼쪽 스테이션 10 (거리 10)
• 차량 24: 25까지 1, 10까지 14 → 25
• 차량 32: 25까지 7, 40까지 8 → 25
• 차량 55: 40까지 15, 70까지 15로 동률 → 좌표가 더 작은 40
• 차량 100: 오른쪽에 스테이션이 없으므로 가장 오른쪽 스테이션 70

예시 2 설명: 18번 스테이션은 점검 중이라 후보에서 제외됩니다. 차량 19는 남은 두 스테이션 5, 33까지의 거리가 모두 14로 동률이므로 좌표가 더 작은 5를 안내합니다.

제약 조건

• 1 ≤ stations.length ≤ 100,000
• available.length === stations.length
• 1 ≤ cars.length ≤ 100,000
• 0 ≤ stations[i] ≤ 1,000,000,000, stations는 엄격히 증가하는 정수 배열
• 0 ≤ cars[j] ≤ 1,000,000,000 (정수, 중복 가능, 정렬되어 있지 않음)
• 반환 배열의 길이는 cars.length와 같아야 합니다.
• 차량 수와 스테이션 수가 모두 크므로, 차량 한 대마다 스테이션 전체를 훑는 풀이는 제한 시간 안에 끝나지 않습니다.

시간 복잡도 목표: O((n + q) log n) (n = 스테이션 수, q = 차량 수)