[프로그래머스 lev3/JS] 이중우선순위 큐

문제 출처

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

나의 풀이

function solution(operations) {
  let queue = []

  for(let i=0; i<operations.length; i++) {
    const [first, second] = operations[i].split(' ')
    
    if(first === 'I') {
      queue.push(Number(second))
    }

    else if(first === 'D' && second === '-1'){
      if(queue.length === 0) continue

      let min = Math.min(...queue)
      queue.splice(queue.indexOf(min), 1)
    }
    else if(first === 'D' && second === '1'){
      if(queue.length === 0) continue

      let max = Math.max(...queue)
      queue.splice(queue.indexOf(max), 1)
    }
  }

  if(queue.length === 0) return [0,0]
  return [Math.max(...queue), Math.min(...queue)]
}

console.log(solution(["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"])); // [0, 0]
console.log(solution(["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"])); // [333, -45]

다른 풀이

어차피 삭제할 때 index가 필요하므로 findIndex를 활용하는 게 좋다.

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];
}

다른 풀이 2

var pq = (function () {
  function PriorityQueue(data, compare) {
    this.data = data || [];
    this.length = this.data.length;
    this.compare = compare || defaultCompare;

    if (this.length > 0) {
      for (var i = (this.length >> 1) - 1; i >= 0; i--) this._down(i);
    }
  }
  function defaultCompare(a, b) {
    return a - b;
  }
  PriorityQueue.prototype = {
    push: function (item) {
      this.data.push(item);
      this.length++;
      this._up(this.length - 1);
    },
    pop: function () {
      if (this.length === 0) return undefined;

      var top = this.data[0];
      this.length--;

      if (this.length > 0) {
        this.data[0] = this.data[this.length];
        this._down(0);
      }
      this.data.pop();

      return top;
    },
    peek: function () {
      return this.data[0];
    },
    _up: function (pos) {
      var data = this.data;
      var compare = this.compare;
      var item = data[pos];

      while (pos > 0) {
        var parent = (pos - 1) >> 1;
        var current = data[parent];
        if (compare(item, current) >= 0) break;
        data[pos] = current;
        pos = parent;
      }
      data[pos] = item;
    },
    _down: function (pos) {
      var data = this.data;
      var compare = this.compare;
      var halfLength = this.length >> 1;
      var item = data[pos];

      while (pos < halfLength) {
        var left = (pos << 1) + 1;
        var right = left + 1;
        var best = data[left];

        if (right < this.length && compare(data[right], best) < 0) {
          left = right;
          best = data[right];
        }
        if (compare(best, item) >= 0) break;

        data[pos] = best;
        pos = left;
      }
      data[pos] = item;
    },
  };

  return PriorityQueue;
})();

function solution(operations) {
  var answer = [];
  const hight = new pq(null, (a, b) => b[0] - a[0]);
  const low = new pq(null, (a, b) => a[0] - b[0]);
  let idx = 0;
  let visited = [];
  
  operations.map((v) => {
    debugger;
    if (v[0] === "I") {
      hight.push([v.substr(1), idx]);
      low.push([v.substr(1), idx++]);
    } else {
      let removed;
      if (v.substr(2) == -1) {
        while ((removed = low.pop())) {
          if (visited[removed[0]] === undefined) {
            visited[removed[0]] = 1;
            break;
          }
        }
      } else {
        while ((removed = hight.pop())) {
          if (visited[removed[0]] === undefined) {
            visited[removed[0]] = 1;
            break;
          }
        }
      }
    }
  });

  let h = 0;
  let l = 0;
  let removed;
  while ((removed = hight.pop())) {
    if (visited[removed[0]] === undefined) {
      h = removed[0];
      break;
    }
  }
  while ((removed = low.pop())) {
    if (visited[removed[0]] === undefined) {
      l = removed[0];
      break;
    }
  }

  return [h ? parseInt(h) : 0, l ? parseInt(l) : 0];
}