99클럽 10일차 TIL (240731)

[Middler] 오늘의 문제 : 이중우선순위큐

걸린시간 : 36분

권장시간 : 1시간

 

오늘의 회고

힙 문제를 풀때마다 파이썬의 heapq 라이브러리를 사용하면 참 간결하다는 생각을 한다. 하지만 이번 문제는 명령어에 따라 최댓값을 추출하고, 최솟값을 추출해야 하기 때문에 약간 분기처리 부분에서 헷갈렸다.

내 생각

[1트]

1. heapq라이브러리를 사용해 I 명령어의 숫자를 삽입한다.

2. D 1인 경우, heap 리스트의 pop()을 통해 삭제해준다.

3. D -1인 경우, heapq.heappop() 라이브러리를 이용해 가장 작은 값을 삭제한다.

 

[문제점] : heapq를 통해 구현한 최소 힙 배열은 마지막 원소가 가장 큰 값이라는 것을 보장하지 않는다.

 

[결론]

2. D 1인 경우, heap 배열의 최댓값을 찾아 remove() 를 통해 삭제해준다.

문제풀이

1. javascript (통과X)

현재 heap을 구현해서 풀어보고 있는데, 테스트 케이스는 모두 통과했으나, 제출 시 통과를 못하고 있다. 어디가 문제일까..? 우선 좀 더 봐바야 겠다.

class MinHeap {
    constructor() {
        this.heap = [];
    }
    size(){
        return this.heap.length;
    }
    max() {
        return Math.max(...this.heap);
    }
    min() {
        return this.heap[0];
    }
    removeMax() {
        let max = this.max();
        let idx = this.heap.indexOf(max);
        if(idx > -1) this.heap.splice(idx, 1);
    }
    swap(idx1, idx2) {
        [this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]];
    }
    add(value) {
        this.heap.push(value);
        this.bubbleUp()
    }
    bubbleUp() {
        let idx = this.heap.length - 1; 
        let parentIdx = Math.floor((idx - 1) / 2);
        
        while(this.heap[parentIdx] && this.heap[idx] < this.heap[parentIdx]) {
            this.swap(idx, parentIdx);
            idx = parentIdx;
            parentIdx = Math.floor((idx - 1) / 2);
        }
    }
    poll(){
        if(this.heap.length === 1) {
            return this.heap.pop();
        }
        const value = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown();
        return value;
    }
    bubbleDown() {
        let idx = 0;
        let leftIdx = idx * 2 + 1;
        let rightIdx = idx * 2 + 2;
        
        while((this.heap[leftIdx] && this.heap[idx] > this.heap[leftIdx]) || (this.heap[rightIdx] && this.heap[idx] > this.heap[rightIdx])) {
            let smallerIdx = leftIdx;
            
            if(this.heap[rightIdx] && this.heap[rightIdx] < this.heap[leftIdx]) {
                smallerIdx = rightIdx;
            }
            
            this.swap(idx, smallerIdx);
            idx = smallerIdx;
            leftIdx = idx * 2 + 1;
            rightIdx = idx * 2 + 2;
        }
    }
}

function solution(operations) {
    var answer = [];
    
    let heap = new MinHeap();
    for (let i=0; i<operations.length; i++){
        let [command, num] = operations[i].split(" ").map((v,i)=> i === 1 ? Number(v) : v);
        
        if(command === "I") {
            heap.add(num);
        } else {
            if (num < 0) {
                heap.poll();
            }else {
                heap.removeMax();
            }
        }
    }
    
    if(heap.size() < 1) {
        answer.push(0)
        answer.push(0)
    } else {
        answer.push(heap.max())
        answer.push(heap.min())
    }
    
    return answer;
}

2.python

import heapq
def solution(operations):
    answer = []
    
    heap = []
    for i in range(len(operations)) :
        command, num = operations[i].split()
        if command == "I" :
            heapq.heappush(heap, int(num))
        elif command == "D" and heap :
            if int(num) < 0 :
                heapq.heappop(heap)
            elif int(num) > 0 :
                heap.remove(max(heap))
                
    if heap :
        answer.append(max(heap))
        answer.append(heap[0])
    else :
        answer.append(0)
        answer.append(0)
    
    return answer

 

느낀 점

- 이중 우선순위큐 문제 그대로 2개의 큐를 두고 풀면 더 쉽다던데 그렇게도 한번 생각해봐야겠다.

---

[Challenger] 오늘의 문제 : 최대 힙

오늘의 회고

python 에서 시간초과가 발생했는데, input() 사용 시 시간이 많이 소요된다고 하여 sys를 이용해서 수정했다. 그러니 잘 해결되었다.

 

내 생각

최대 힙은 값이 큰 수를 루트노드로 가게끔 하면 된다. 때문에 생각의 흐름은 아래와 같다.

1. n을 입력받는다.

2. 1부터 n까지 입력받으면서 입력되는 문자열에 따라 0이고 큐가 비어있지 않다면 큐의 루트노드를 뽑고, 큐가 0이고 비어있다면 0을 추출한다.

3. 문자열이 0이 아니면 큐에 넣는다.

 

문제풀이

1. javascript

/**
 * 최대 힙 js로 구현해보기
 */
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

// 최대 힙 클래스
let N = Number(input[0]);

class MaxHeap {
  constructor() {
    this.heap = [];
  }
  size() {
    return this.heap.length;
  }
  swap(idx1, idx2) {
    [this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]];
  }
  add(value) {
    this.heap.push(value);
    this.bubbleUp();
  }
  bubbleUp() {
    let index = this.heap.length - 1;
    let parentIdx = Math.floor((index - 1) / 2);

    while (this.heap[parentIdx] && this.heap[parentIdx] < this.heap[index]) {
      this.swap(index, parentIdx);
      index = parentIdx;
      parentIdx = Math.floor((index - 1) / 2);
    }
  }
  poll() {
    if (this.heap.length === 1) {
      return this.heap.pop();
    }
    const value = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown();
    return value;
  }
  bubbleDown() {
    let index = 0;
    let leftIdx = index * 2 + 1;
    let rightIdx = index * 2 + 2;

    while (
      (this.heap[leftIdx] && this.heap[index] < this.heap[leftIdx]) ||
      (this.heap[rightIdx] && this.heap[index] < this.heap[rightIdx])
    ) {
      let biggerIdx = leftIdx;

      if (this.heap[rightIdx] && this.heap[leftIdx] < this.heap[rightIdx]) {
        biggerIdx = rightIdx;
      }

      this.swap(index, biggerIdx);
      index = biggerIdx;
      leftIdx = index * 2 + 1;
      rightIdx = index * 2 + 2;
    }
  }
}

// 우선순위 큐 클래스
class PriorityQueue extends MaxHeap {
  constructor() {
    super();
  }
  enqueue = (val) => this.add(val);
  dequeue = () => this.poll();
  isEmpty = () => {
    return this.heap.length < 1;
  };
}

const q = new PriorityQueue();
let answer = [];
// let n = Number(input[0]);

for (let i = 1; i <= N; i++) {
  let num = Number(input[i]);

  if (num === 0) {
    if (q.isEmpty()) {
      answer.push(0);
    } else {
      answer.push(q.dequeue());
    }
  } else {
    q.enqueue(num);
  }
}

console.log(answer.join("\n"));

 

2.python

import heapq
import sys

n = int(sys.stdin.readline())
heap = []
answer = []

for i in range(n) :
    num = int(sys.stdin.readline())
    
    if num > 0 :
        heapq.heappush(heap, -1 * num)
    else :
        if not heap :
            answer.append(0)
        else :
            answer.append(-heapq.heappop(heap))

print('\n'.join(map(str, answer)))

 

느낀 점

파이썬에서 input() 보다 sys라이브러리를 사용해 시간 효율성을 높이자.