[JS] 이중우선순위큐

이분탐색을 활용해서 풀었다.

 

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

프로그래머스

 

 

 

결국 문제에서 요구하는 것은 3개이다.

최소 , 최대를 바로바로 빼낼 수 있게 도와주는것 . 이분탐색을 활용하여 항상 정렬된 형태로 값을 넣는다면 문제를 해결할 수 있을것이라 생각했다.

 

이분탐색으로 정렬된 리스트에 값을 넣는것을 빠르게 했고  pop은 시간복잡도가 O(1) 이므로 괜찮을꺼라 생각했다. 조금 주의할점은 shift로 JS에서 shift는 O(n)의 시간복잡도를 가지게 된다.

 

해당 처리를 따로 해주지는 않았는데도 문제는 통과가 되었다.

 

만약 해당 부분때문에 통과가 안되었다면 startIdx라는 변수를 둬서 삭제를 하지 않고 시작점만 바꾸는 방식으로 구현했을 것 같다.

 

 

 

 

function solution(operations) {
    
    
    const push = (value,ary) =>{
        if(value.length<1) {
            ary.push(value)
            return
        }

        let [left,right] = [0,ary.length-1]
        while(left <= right){
            const mid = ~~((left + right) / 2)
            if(ary[mid] < value) left = mid + 1
            else right = mid - 1
        }
        return [...ary.slice(0,left),value,...ary.slice(left)]
    }
    
    let ary = []
    for (const operation of operations){
        
        const [order,val] = operation.split(" ")
        if (order ==='I') ary = push(+val,ary)
        else if(val==="1") ary.pop()
        else ary.shift()
    }
    
    return ary.length>0 ? [ary[ary.length-1],ary[0]] : [0,0]
}