프로그래머스 [Lv. 0] 수열과 구간 쿼리 2 {언어 : JavaScript}

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/181923

프로그래머스

정답 코드

function solution(arr, queries) {
    const answer = [];
    queries.forEach(([s, e, k]) => {
        // s부터 e까지의 부분 배열을 복사하고 정렬한다.
        const newArr = arr.slice(s, e + 1).sort((a, b) => a - b);
        
        // 이분 탐색을 위한 초기값 설정
        let left = 0; // 시작 인덱스는 0
        let right = e - s; // 배열의 끝 인덱스
        
        // 찾고자 하는 값의 위치를 저장할 변수
        let position = -1;
        
        // 이분 탐색 시작
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (newArr[mid] > k) {
                position = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        // 찾은 위치에 따라 결과값을 결정
        if (position !== -1) {
            answer.push(newArr[position]);
        } else {
            answer.push(-1);
        }
    });
    return answer;
}

풀이 방법

1. forEach의 원소로 arr을 슬라이싱 한다.
   1. arr.slice(e, s+1)
2. 슬라이싱 한 배열을 정렬한다.
   1. arr.sort((a, b) => a - b) 오름 차순
   2. arr.sort((a, b) => b - a) 내림 차순
3. 정렬한 배열을 이분탐색을 통해 k보다 큰 index를 찾아준다.
4. position이 -1인 경우는 k보다 큰 숫자가 없다는 말이므로 -1을 push

느낀점

• 이분탐색을 할 때 처음과 끝 부분의 값을 실수하지 말자.