Portfolio

문제

풀이

재영


class MaxHeap {
  constructor() {
    this.heap = [null];
  }

  heappush(val) {
    this.heap.push(val);
    let nowIndex = this.heap.length - 1;
    let parentIndex = Math.floor(nowIndex / 2);

    while (nowIndex > 1 && this.heap[nowIndex] > this.heap[parentIndex]) {
      this.swap(nowIndex, parentIndex);
      nowIndex = parentIndex;
      parentIndex = Math.floor(nowIndex / 2);
    }
  }

  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 [nowIndex, leftIndex, rightIndex] = [1, 2, 3];

    if (this.heap[leftIndex] === undefined) {
      return min;
    }

    if (this.heap[rightIndex] === undefined) {
      if (this.heap[leftIndex] > this.heap[nowIndex]) {
        this.swap(leftIndex, nowIndex);
        return min;
      }
    }

    while (
      this.heap[leftIndex] > this.heap[nowIndex] ||
      this.heap[rightIndex] > this.heap[nowIndex]
    ) {
      const minIndex =
        this.heap[leftIndex] < this.heap[rightIndex] ? rightIndex : leftIndex;

      this.swap(nowIndex, minIndex);
      nowIndex = minIndex;
      leftIndex = nowIndex * 2;
      rightIndex = nowIndex * 2 + 1;
    }

    return min;
  }

  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }

  head() {
    return this.heap[1];
  }

  getLength() {
    return this.heap.length - 1;
  }
} // 최대힙을 위하여

const solution = (n, works) => {
  let answer = 0; // 결과 값
  const maxHeap = new MaxHeap();

  works.forEach((work) => maxHeap.heappush(work));

  let maxFatigue = maxHeap.heappop();
  let poppedWorksCount = 1;

  while (maxHeap.head() && n > 0) {
    const nowFatigue = maxHeap.heappop();

    if (maxFatigue === nowFatigue) {
      poppedWorksCount += 1;
    } else {
      const diff = maxFatigue - nowFatigue;

      if (diff * poppedWorksCount > n) {
        maxHeap.heappush(nowFatigue);
        break;
      }

      n -= poppedWorksCount * diff;

      poppedWorksCount += 1;
      maxFatigue = nowFatigue;
    }
  }

  if (n) {
    const quotient = parseInt(n / poppedWorksCount); // 빼낸 카운트 개수
    const remainder = n % poppedWorksCount;
		
    maxFatigue -= quotient; // 최대피로도에서 뺄 수 있는 시간(공통) 
    if (maxFatigue <= 0) return 0;

    answer += Math.pow(maxFatigue, 2) * (poppedWorksCount - remainder);
    answer += Math.pow((maxFatigue - 1), 2) * remainder;
  } else {
    answer += Math.pow(maxFatigue, 2) * poppedWorksCount;
  }

  if (maxHeap.head()) {
    answer += maxHeap.heap.reduce((acc, cur) => {
      return acc + Math.pow(cur || 0, 2);
    }, 0);
  } // 안빠진 것들 계산

  return answer;
};

효성


class Heap {
  constructor() {
    this.heap = [];
  }
  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;
  }
}


function solution(n, works) {
    let answer = 0;
    const heap = new Heap;
    works.forEach(work => heap.push(work));
    
    for(let i=0; i<n; i++) {
        const maxNum = heap.pop() - 1;
        if(maxNum) {
            heap.push(maxNum);
        }
    }
    
    heap.heap.forEach(work => answer += work**2);
    
    return answer;
}

은찬


class PriorityQueue {
    constructor(){
        this.queue = [0];
        this.size = 0;
    }
    
    push(value) {
        this.queue.push(value);
        this.size++;
        
        this.moveUp(this.size);
    }
    
    moveUp(index){
        while(Math.floor(index / 2)){
            const parent = Math.floor(index / 2);
            
            if(this.queue[parent] < this.queue[index]){
                [this.queue[parent], this.queue[index]] = [this.queue[index], this.queue[parent]];
            }
            
            index = parent;
        }
    }
    
    pop() {
        const maxValue = this.queue[1];
        this.queue[1] = this.queue[this.size];
        
        this.queue.pop();
        this.size--;
        
        this.moveDown(1);
        
        return maxValue;
    }
    
    moveDown(index) {
        while(index * 2 <= this.size){
            const maxChildIndex = this.findMaxChildIndex(index);
            
            if(this.queue[index] < this.queue[maxChildIndex]){
                const tmp = this.queue[maxChildIndex];
                this.queue[maxChildIndex] = this.queue[index];
                this.queue[index] = tmp;
            }
            
            index = maxChildIndex;
        }
    }
    
    findMaxChildIndex(index) {
        const left = index * 2;
        const right = (index * 2) + 1;
        
        if(right > this.size){
            return left;
        } else{
            if(this.queue[right] > this.queue[left]){
                return right;
            } else{
                return left;
            }
        }
    }    
}

function solution(n, works) {
    let answer = 0;
    const heap = new PriorityQueue();
    
    for(let i = 0; i < works.length; i++){
        heap.push(works[i]);
    }
    
    for(let i = 0; i < n; i++){
        const work = heap.pop();

        if(work !== 0){
            heap.push(work - 1);
        }
    }
    
    while(heap.size){
        const work = heap.pop();
        
        answer += (work ** 2);
    }
    
    return answer;
}

야근 지수

문제

풀이