Portfolio

문제

풀이

은찬


const findKthLargest = (nums, k) => {    
    return nums.sort((a, b) => b - a)[k - 1];
};

혹시 오늘 못들어 갈 수 있어서 설명 남길게요~

단 한줄로 만들 수 있어서 한줄만 남깁니다 하하

주어진 nums를 내림차순으로 정렬한 후 k - 1 번째에 있는 수를 리턴하면 됩니다!

끝!

효성


var findKthLargest = function(nums, k) {
    nums.sort((a,b) => b-a);
    return nums[k-1];
};

heap으로 풀어봤어요!

근데 왜 더 오래 걸릴까요...?

⇒ 힙은 데이터를 넣을 때마다 비교를 하면서 정렬을 하기 때문에, 한꺼번에 sorting 하는 것보다 느릴 거에요! feat.교수은찬

추가설명) 한번의 sort만 필요한 경우엔 sort를, 실시간으로 추가와 삭제가 여러 번 이루어질 경우 heap을 사용하는게 좋다고 합니다. ex) 10만개의 데이터에서 3만 개의 데이터를 다시 넣고 넣을 때마다 가장 큰 데이터를 구하라 한다면? (그리디적으로 생각하지 않았을 때) sort → 30000개의 데이터를 for문으로 돌리고 넣는 과정에서 또 정렬을 해야 함(30000 * n log n) heap → 그냥 기존 for문에서 삽입 로직만 하면 됨(30000 * log n) feat. 조교재영


class MyHeap {
  constructor() {
    this.heap = []; // n:parent, 2*n+1:left child, 2*n+2:right child
  }
  size() {
    return this.heap.length;
  }
  push(node) {
    this.heap.push(node);
    let curIdx = this.heap.length - 1;
    let parentIdx = Math.floor((curIdx - 1) / 2);

    while (this.heap[parentIdx] < this.heap[curIdx]) {
      [this.heap[parentIdx], this.heap[curIdx]] = [
        this.heap[curIdx],
        this.heap[parentIdx],
      ];
      curIdx = parentIdx;
      parentIdx = Math.floor((curIdx - 1) / 2);
    }
  }

  pop() {
    let lastIdx = this.heap.length - 1;
    let curIdx = 0;
    [this.heap[curIdx], this.heap[lastIdx]] = [
      this.heap[lastIdx],
      this.heap[curIdx],
    ];
    const result = this.heap.pop();
    lastIdx = this.heap.length - 1;

    while (curIdx < lastIdx) {
      let leftIdx = curIdx * 2 + 1;
      let rightIdx = curIdx * 2 + 2;
      if (this.heap[leftIdx] == null) break;
      if (this.heap[rightIdx] == null) {
        if (this.heap[curIdx] < this.heap[leftIdx]) {
          [this.heap[curIdx], this.heap[leftIdx]] = [
            this.heap[leftIdx],
            this.heap[curIdx],
          ];
        }
        curIdx = leftIdx;
        break;
      }

      if (
        this.heap[curIdx] < this.heap[leftIdx] ||
        this.heap[curIdx] < this.heap[rightIdx]
      ) {
        const maxIdx =
          this.heap[leftIdx] > this.heap[rightIdx] ? leftIdx : rightIdx;
        [this.heap[curIdx], this.heap[maxIdx]] = [
          this.heap[maxIdx],
          this.heap[curIdx],
        ];
        curIdx = maxIdx;
      } else {
        break;
      }
    }
    return result;
  }
}

var findKthLargest = function(nums, k) {
    const heap = new MyHeap();
    
    nums.forEach(num => heap.push(num));
    for(let i=0; i<k-1; i++) {
        heap.pop();
    }
    return heap.pop()
};

희진


var findKthLargest = function(nums, k) {
    return nums.sort((a,b)=>b-a)[k-1]
};

재영

minHeap


class MinHeap {
  constructor() {
    this.heap = [null];
  }
  heappush(val) {
    this.heap.push(val);
    let nowIdx = this.heap.length - 1;
    let parentIdx = this.updateParentIndex(nowIdx);
    while (nowIdx > 1 && this.heap[nowIdx] < this.heap[parentIdx]) {
      this.swap(nowIdx, parentIdx);
      nowIdx = parentIdx;
      parentIdx = this.updateParentIndex(nowIdx);
    }
  }
  heappop() {
    if (this.heap.length === 1) return;
    if (this.heap.length === 2) return this.heap.pop();
    const min = this.heap[1];
    this.heap[1] = this.heap.pop();
    let [nowIdx, leftIdx, rightIdx] = this.updateIndices(1);
    if (!this.heap[leftIdx]) return min;
    if (!this.heap[rightIdx]) {
      if (this.heap[leftIdx] < this.heap[nowIdx]) {
        this.swap(leftIdx, nowIdx);
      }
      return min;
    }
    while (
      Math.min(this.heap[leftIdx], this.heap[rightIdx]) < this.heap[nowIdx]
    ) {
      const minIdx =
        this.heap[leftIdx] < this.heap[rightIdx] ? leftIdx : rightIdx;
      this.swap(nowIdx, minIdx);
      [nowIdx, leftIdx, rightIdx] = this.updateIndices(minIdx);
    }
    return min;
  }
  updateParentIndex(idx) {
    return Math.floor(idx / 2);
  }
  updateIndices(idx) {
    return [idx, idx * 2, idx * 2 + 1];
  }
  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }
}

maxHeap


class MaxHeap {
  constructor() {
    this.heap = [null];
  }
  heappush(val) {
    this.heap.push(val);
    let nowIdx = this.heap.length - 1;
    let parentIdx = this.updateParentIndex(nowIdx);
    while (nowIdx > 1 && this.heap[nowIdx] > this.heap[parentIdx]) {
      this.swap(nowIdx, parentIdx);
      nowIdx = parentIdx;
      parentIdx = this.updateParentIndex(nowIdx);
    }
  }
  heappop() {
    if (this.heap.length === 1) return;
    if (this.heap.length === 2) return this.heap.pop();
    const max = this.heap[1];
    this.heap[1] = this.heap.pop();
    let [nowIdx, leftIdx, rightIdx] = this.updateIndices(1);
    if (!this.heap[leftIdx]) return max;
    if (!this.heap[rightIdx]) {
      if (this.heap[leftIdx] > this.heap[nowIdx]) {
        this.swap(leftIdx, nowIdx);
      }
      return max;
    }
    while (
      Math.max(this.heap[leftIdx], this.heap[rightIdx]) > this.heap[nowIdx]
    ) {
      const maxIdx =
        this.heap[leftIdx] > this.heap[rightIdx] ? leftIdx : rightIdx;
      this.swap(nowIdx, maxIdx);
      [nowIdx, leftIdx, rightIdx] = this.updateIndices(maxIdx);
    }
    return max;
  }
  updateParentIndex(idx) {
    return Math.floor(idx / 2);
  }
  updateIndices(idx) {
    return [idx, idx * 2, idx * 2 + 1];
  }
  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }
}


class MaxHeap {
  constructor() {
    this.heap = [null];
  }
  heappush(val) {
    this.heap.push(val);
    let nowIdx = this.heap.length - 1;
    let parentIdx = this.updateParentIndex(nowIdx);
    while (nowIdx > 1 && this.heap[nowIdx] > this.heap[parentIdx]) {
      this.swap(nowIdx, parentIdx);
      nowIdx = parentIdx;
      parentIdx = this.updateParentIndex(nowIdx);
    }
  }
  heappop() {
    if (this.heap.length === 1) return;
    if (this.heap.length === 2) return this.heap.pop();
    const max = this.heap[1];
    this.heap[1] = this.heap.pop();
    let [nowIdx, leftIdx, rightIdx] = this.updateIndices(1);
    if (!this.heap[leftIdx]) return max;
    if (!this.heap[rightIdx]) {
      if (this.heap[leftIdx] > this.heap[nowIdx]) {
        this.swap(leftIdx, nowIdx);
      }
      return max;
    }
    while (
      Math.max(this.heap[leftIdx], this.heap[rightIdx]) > this.heap[nowIdx]
    ) {
      const maxIdx =
        this.heap[leftIdx] > this.heap[rightIdx] ? leftIdx : rightIdx;
      this.swap(nowIdx, maxIdx);
      [nowIdx, leftIdx, rightIdx] = this.updateIndices(maxIdx);
    }
    return max;
  }
  updateParentIndex(idx) {
    return Math.floor(idx / 2);
  }
  updateIndices(idx) {
    return [idx, idx * 2, idx * 2 + 1];
  }
  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }
}

const findKthLargest = function (nums, k) {
  const maxHeap = new MaxHeap();
  nums.forEach((num) => maxHeap.heappush(num));
  let i = 0;
  let result;
  while (i < k) {
    i += 1;
    result = maxHeap.heappop();
  }
  return result;
};

Kth Largest Element in an Array

문제

풀이

heap으로 풀어봤어요!