각 체크포인트에서 받을 수 있는 최대 신호
자바스크립트 코딩테스트 문제로 li-chao-tree 주제를 연습해보세요. 난이도는 hard이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
여러 신호선 y = mx + b 가 있을 때, 각 체크포인트 위치 x에서 받을 수 있는 최대 신호값을 구하는 문제입니다.
문제 설명
정수 쌍 배열 lines와 정수 배열 queries가 주어집니다.
lines[i] = [m, b]는 신호선y = m * x + b를 뜻합니다.queries[j]는 체크포인트의 x좌표입니다.
각 체크포인트 위치 x = queries[j] 에서 모든 신호선 값을 계산했을 때,
그중 가장 큰 값을 구해 순서대로 배열에 담아 반환하는 maximumSignalAtCheckpoints 함수를 작성하세요.
반환 배열의 j번째 값은 아래와 같습니다.
max(m * queries[j] + b) for every [m, b] in lines
제한사항
1 <= lines.length <= 200,0001 <= queries.length <= 200,000-1,000,000,000 <= m, b <= 1,000,000,000-1,000,000,000 <= queries[j] <= 1,000,000,000- 모든 계산 결과는 JavaScript의 안전한 정수 범위 안에 들어온다고 가정합니다.
- 가능한 한
O((n + q) log C)수준으로 해결해 보세요. (C는 x좌표 범위)
예시
- 입력:
lines = [[2, 3], [-1, 10], [0, 5]]queries = [-2, 0, 4]
- 출력:
[12, 10, 11]
설명:
x = -2일 때 값들은-1,12,5이므로 최대는12x = 0일 때 값들은3,10,5이므로 최대는10x = 4일 때 값들은11,6,5이므로 최대는11
힌트
- 쿼리마다 모든 직선을 다 계산하면
O(lines.length * queries.length)가 되어 너무 느립니다. - 필요한 것은 직선들의 교점을 직접 모두 구하는 것이 아니라, 특정
x에서 가장 위에 있는 직선이 무엇인지 빠르게 찾는 구조입니다. - 기울기 정렬이나 쿼리 정렬이 보장되지 않으므로, x축 구간을 기준으로 직선을 관리하는 방법을 떠올려 보세요.
해설
각 질의마다 모든 직선을 대입하면 최악의 경우 200,000 × 200,000 이라 불가능합니다.
이 문제의 핵심은 직선을 하나씩 저장해 두고, 어떤 x좌표가 들어왔을 때 그 지점에서의 최대값만 빠르게 찾는 것입니다. 이를 위해 사용할 수 있는 대표적인 자료구조가 Li Chao Tree 입니다.
1. Li Chao Tree가 하는 일
Li Chao Tree는 x축 구간을 기준으로 세그먼트 트리처럼 나누면서, 각 노드에 “이 구간에서 현재 가장 유망한 직선” 하나를 저장합니다.
새 직선을 넣을 때는
- 구간의 왼쪽 끝,
- 중간점,
- 오른쪽 끝 근처에서 기존 직선과 새 직선을 비교해 어느 쪽 구간에서 누가 더 유리한지 판단하고, 밀린 직선만 필요한 자식 구간으로 내려보냅니다.
이 과정을 반복하면 직선 하나 삽입이 O(log C) 안에 끝납니다.
2. 왜 이 구조가 필요한가?
다른 볼록 껍질 최적화 방법들은 보통
- 기울기가 정렬되어 들어오거나
- 질의 x가 단조롭게 들어오는 조건이 있어야 깔끔합니다.
하지만 이 문제는
- 기울기 순서가 제멋대로일 수 있고
- 질의 순서도 섞여 있고
- x가 음수와 양수 전부 가능하며 범위도 매우 큽니다.
그래서 “x좌표 기준으로 비교하는 자료구조”가 더 잘 맞습니다.
3. 풀이 흐름
- 모든
queries의 최솟값과 최댓값을 구합니다. - 그 x구간 위에 Li Chao Tree를 만듭니다.
lines의 모든 직선을 트리에 삽입합니다.- 각
queries[j]에 대해 트리에서 최대값을 질의합니다. - 결과를 배열로 반환합니다.
4. 예시 흐름
lines = [[2, 3], [-1, 10], [0, 5]] 라면
세 직선을 트리에 넣어 둡니다.
그 뒤
x = -2질의 →12x = 0질의 →10x = 4질의 →11
을 빠르게 구할 수 있습니다.
5. 복잡도
- 직선 삽입: 각
O(log C) - 질의: 각
O(log C) - 전체:
O((n + q) log C)
여기서 C는 x좌표 범위의 크기입니다.
정렬이 필요 없는 강력한 직선 최대/최소 질의 구조라는 점이 이 문제의 포인트입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.