구간 고유 점수 순위 조회

문제

리그 운영진은 경기마다 기록된 점수를 배열 scores에 순서대로 저장해 두었습니다. 운영진은 특정 구간에서 서로 다른 점수만 추려 낮은 순으로 매긴 순위를 자주 조회합니다.

각 질의 queries[q] = [l, r, k]를 다음과 같이 처리하세요.

1. scores의 l번째부터 r번째까지(1부터 세는 번호, 양 끝 포함)를 꺼낸다
2. 그중 중복된 점수는 하나만 남기고 오름차순으로 정렬한다
3. 정렬 결과의 k번째 값을 답으로 한다. 값이 k개보다 적으면 -1을 답으로 한다

모든 질의의 답을 순서대로 배열에 담아 반환하세요.

function solution(scores: number[], queries: number[][]): number[]

예시

scores = [8,3,8,5,3,9,1], queries = [[1,4,2],[2,6,4],[3,3,1],[1,7,6]] → [5,9,8,-1]

scores = [4,4,4,4], queries = [[1,4,1],[1,4,2]] → [4,-1]

제약 조건

• 1 ≤ scores.length ≤ 1,000
• 1 ≤ scores[i] ≤ 1,000,000
• 1 ≤ queries.length ≤ 100
• 각 질의는 1 ≤ l ≤ r ≤ scores.length, 1 ≤ k ≤ scores.length를 만족합니다
• k가 구간의 고유 점수 개수보다 클 수 있습니다

시간 복잡도 목표: O(Q × N log N)