[Algorithm] 이중우선순위큐 - JavaScript

 

프로그래머스 - 이중우선순위큐

난이도 : Level 3
정답률: 60% 3단계 중 제일 정답률이 높다

▶ 문제

 

 

▶ 풀이

문자열이 I 로 시작하면 answer 배열에 삽입하고 D 로 시작하면 정렬 후 명령에 따라 최대값과 최솟값을 제거한다.

function solution(operations) {
    var answer = [];
    operations.forEach(x => {
        if(x[0] === 'I') {
            answer.push(parseInt(x.split('I ')[1]));
        } else {
            answer.sort((a, b) => a - b);
            if(x[2] === '-') {
                answer.shift();
            } else {
                answer.pop();
            }
        }
    })
    answer.sort((a, b) => a - b);
    return answer.length === 0 ? [0, 0] : [answer[answer.length - 1], answer[0]];
}

JS 에 sort() 는 Tim Sort 는 사용한다.

Tim Sort 는 데이터의 특성을 고려하여 더욱 빠르게 고안된 알고리즘으로 최선의 시간 복잡도는
O(n), 평균은 O(nlogn), 최악의 경우 시간 복잡도는 O(nlogn)이다. Tim sort는 안정적인 두 정렬 방법을 결합했기에 안정적이며, 추가 메모리는 사용하지만 기존의 Merge sort에 비해 적은 추가 메모리를 사용하여 다른 O(nlogn) 정렬 알고리즘의 단점을 최대한 극복한 알고리즘이다.
출처 ㅣ https://d2.naver.com/helloworld/0315536

▶ 다른 사람의 풀이

function solution(arg) {
    var list = [];
    arg.forEach(t => {
        if (t[0] === 'I') {
            list.push(+(t.split(" ")[1]));
        } else {
            if (!list.length) return;

            var val = (t[2] === '-' ? Math.min : Math.max)(...list);
            var delIndex = list.findIndex(t => t === val);

            list.splice(delIndex, 1);
        }
    })

    return list.length ? [Math.max(...list), Math.min(...list)] : [0, 0];

Math.max 와 Math.min 을 사용해서 풀었다.

▶ 마치며

다른 사람의 풀이는 시간복잡도가 n(3n) 이고 내 풀이는 n(nLogn + n)인데, 주어진 테스트 케이스에선 내 코드가 더 빨랐다. 생각보다 nLogN 의 시간복잡도가 나쁘지 않은가보다