[JavaScript] 프로그래머스 - 이중우선순위큐 (3단계)

코딩 테스트 풀이 체크리스트
2시간 내에 풀었는가?	O
본인의 실력으로 풀었는가?	O

 

프로그래머스

 

 

 

 

 

function solution(operations) {
    let min = new MinHeap();
    let max = new MaxHeap();
    
    for (let i = 0; i < operations.length; i++) {
        let s = operations[i].split(" ");
        
        if (s[0] === "I") {
            let num = parseInt(s[1]);
            min.add(num);
            max.add(num);
        } else {
            if (s[1] == "1") {
                max.delete();
            } else {
                min.delete();
            }
            
            if (min.length() == 1 || max.length() == 1 || min.top() > max.top()) {
                min = new MinHeap();
                max = new MaxHeap();
            }
        }
    }
    
    return min.length() == 1 || max.length() == 1 ? [0, 0] : [max.top(), min.top()];
}

class MinHeap {
    constructor(){
        this.list = [];
        this.list.push(0);
    }

    add = function(num) {
        this.list.push(num);
        var position = this.list.length-1;
        while(position > 1 && this.list[parseInt(position/2)] > this.list[position]) {
            var parent = parseInt(position / 2);
            
            var temp = this.list[position];
            this.list[position] = this.list[parent];
            this.list[parent] = temp;
            position = parent;
        }
    }
    
    delete = function(num) {
        if (this.list.length == 1) return;
        if (this.list.length == 2) return this.list.pop();
        
        let result = this.list[1];
        
        this.list[1] = this.list.pop();
        let position = 1;
        
        while (position * 2 < this.list.length) {
            let min = this.list[position*2];
            let minPosition = position * 2;
            
            if (minPosition + 1 < this.list.length && min > this.list[minPosition+1]) {
                min = this.list[minPosition+1];
                minPosition += 1;
            }
            
            if (this.list[position] < min) break;
            
            let temp = this.list[position];
            this.list[position] = min;
            this.list[minPosition] = temp;
            
            position = minPosition;
        }
    }
    
    top = function() {
        return this.list[1];
    }
    
    length = function() {
        return this.list.length;
    }
}

class MaxHeap {
    constructor(){
        this.list = [];
        this.list.push(0);
    }

    add = function(num) {
        this.list.push(num);
        var position = this.list.length-1;
        while(position > 1 && this.list[parseInt(position/2)] < this.list[position]) {
            var parent = parseInt(position / 2);
            
            var temp = this.list[position];
            this.list[position] = this.list[parent];
            this.list[parent] = temp;
            position = parent;
        }
    }
    
    delete = function(num) {
        if (this.list.length == 1) return;
        if (this.list.length == 2) return this.list.pop();
        
        let result = this.list[1];
        
        this.list[1] = this.list.pop();
        let position = 1;
        
        while (position * 2 < this.list.length) {
            let max = this.list[position*2];
            let maxPosition = position * 2;
            
            if (maxPosition + 1 < this.list.length && max < this.list[maxPosition+1]) {
                max = this.list[maxPosition+1];
                maxPosition += 1;
            }
            
            if (this.list[position] > max) break;
            
            let temp = this.list[position];
            this.list[position] = max;
            this.list[maxPosition] = temp;
            
            position = maxPosition;
        }
    }
    
    top = function() {
        return this.list[1];
    }
    
    length = function() {
        return this.list.length;
    }
}

 

테스트 1 〉	통과 (0.45ms, 30.3MB)
테스트 2 〉	통과 (0.31ms, 30MB)
테스트 3 〉	통과 (0.45ms, 30MB)
테스트 4 〉	통과 (0.40ms, 30.1MB)
테스트 5 〉	통과 (0.36ms, 30.2MB)
테스트 6 〉	통과 (0.49ms, 30.1MB)

 

 

 

 

 

우선순위큐를 자바스크립트에선 사용해본 적도 없어서.. 그냥 생성자를 이용해서 최소힙과 최대힙을 구현했다.

 

 

 

 

 

function solution(operations) {
    let list = new Array();
    
    for (let i = 0; i < operations.length; i++) {
        let s = operations[i].split(" ");
        if (s[0] == "I") {
            list.push(parseInt(s[1]));
            list.sort(function(a, b) {
                return a - b;
            });
        } else {
            if (s[1] == "1") {
                list.pop();
            } else {
                list.shift();
            }
        }
    }
    return list.length == 0 ? [0, 0] : [list[list.length-1], list[0]];
}

 

테스트 1 〉	통과 (0.10ms, 30MB)
테스트 2 〉	통과 (0.11ms, 30.1MB)
테스트 3 〉	통과 (0.16ms, 30.2MB)
테스트 4 〉	통과 (0.09ms, 30MB)
테스트 5 〉	통과 (0.10ms, 29.9MB)
테스트 6 〉	통과 (0.13ms, 30.2MB)

 

 

 

 

 

근데 그냥 데이터 추가할 때마다 정렬해도 시간 초과 안뜨네... 쩝;;