[JS] 프로그래머스_level 3_야근 지수

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12927#

프로그래머스

 

문제 접근 방법

이번 문제는 (잔업)^2 들의 합이 최소값을 구하는 문제다.

 

이 문제를 보고 두가지 포인트를 잡았다.

 

첫 번째 정렬, 두 번째 최대값 활용

 

풀이 방법은 최대힙과 그리디를 이용한 값의 표준편차를 줄이는 풀이 두 가지가 있다. 물론 두 방법 모두 최대값과 나머지 값들을 비교해 표준편차를 줄이는 방법이다.

 

최대힙을 이용한 풀이

우선 최대힙을 이용해 문제 풀이를 하기 전에 힙 Class를 구현해야한다.

class MaxHeap {
    constructor() {
        this.heap = [];
    }
    push(n){
        this.heap.push(n);
        this.heapifyUp();
    }
    
    pop(){
        if(this.heap.length === 0) return null;
        let root = this.heap[0];
        const lastNode = this.heap.pop();
        
        if(this.heap.length > 0) {
            this.heap[0] = lastNode;
            this.heapifyDown();
        }
        return root;
    }
    
    swap(a, b){
        [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
    }
    
    heapifyUp(){
        let index = this.heap.length - 1;
        while(index > 0){
            const parentIdx = Math.floor((index - 1) / 2);
            if(this.heap[index] <= this.heap[parentIdx]) break;
            this.swap(index, parentIdx);
            index = parentIdx;
        }
    }
    
    heapifyDown() {
    let index = 0;

    while (true) {
      let biggest = index;
      const leftChildIndex = 2 * index + 1;
      const rightChildIndex = 2 * index + 2;

      if ( this.heap[leftChildIndex] && this.heap[leftChildIndex] > this.heap[biggest] ) {
        biggest = leftChildIndex;
      }

      if ( this.heap[rightChildIndex] && this.heap[rightChildIndex] > this.heap[biggest] ) {
        biggest = rightChildIndex;
      }
      // 좌우 자식 모두 없는 경우
      if (biggest === index) break;

      this.swap(index, biggest);
      index = biggest;
    }
  }
}

 

힙의 구현에 대한 내용은 링크를 참고하자....

자료구조 / 힙 Heap

 

힙이 구현됬다면 solution 함수 코드를 작성해 보자.

 

우선 주어진 잔업을 정렬해주었다. 이 작업은 해도되고 안해도 되지만, heapifyUp 동작이 많이 동작해 동작 속도가 느려지는 것을 조금이나마 방지하기 위해 잔업을 정렬한 뒤 push해 주었다.

const sortedWorks = works.sort((a, b) => b - a);
...
for(let i = 0; i < len; i++){
    heap.push(sortedWorks[i]);
}

 

heap에 모든 잔업들이 들어갔다면, 이제 heap의 최대값을 pop해와 -1씩 더해주는 작업을 총 n 번 반복한다. 이 로직에서 만약 최대힙의 최대값으로 0이 나온다면 이것은 힙에 존재하는 값들을 더이상 없거나 0이하라는 의미로 더이상 진행할 잔업이 없음을 의미하기에 답을 0으로 반환해준다.

 

해당 로직은 아까 이야기 했던 각 값들의 표준편차를 줄이는 작업으로 최대힙에서 최대값을 가져와 -1을 더한 값을 다시 힙에 push하고 다시 버블업 하는 과정이 담겨있다. 이런 로직으로 새로운 최대값을 하나씩 -1을 더해주며 각 잔업값들의 표준편차를 줄일 수 있다.

 

이제 n 번만큼 동작했다면, 제곱한 값들의 합을 구하면 된다.

for(let i = 0; i < len; i++){
    answer += heap.pop() ** 2;
}

 

이 로직또한 heap에서 하나씩 pop한 값의 제곱을 answer 변수에 더해주며 최종적으로 재출할 답을 구한다.

 

코드

class MaxHeap {
    constructor() {
        this.heap = [];
    }
    push(n){
        this.heap.push(n);
        this.heapifyUp();
    }
    
    pop(){
        if(this.heap.length === 0) return null;
        let root = this.heap[0];
        const lastNode = this.heap.pop();
        
        if(this.heap.length > 0) {
            this.heap[0] = lastNode;
            this.heapifyDown();
        }
        return root;
    }
    
    swap(a, b){
        [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
    }
    
    heapifyUp(){
        let index = this.heap.length - 1;
        while(index > 0){
            const parentIdx = Math.floor((index - 1) / 2);
            if(this.heap[index] <= this.heap[parentIdx]) break;
            this.swap(index, parentIdx);
            index = parentIdx;
        }
    }
    
    heapifyDown() {
    let index = 0;

    while (true) {
      let biggest = index;
      const leftChildIndex = 2 * index + 1;
      const rightChildIndex = 2 * index + 2;

      if ( this.heap[leftChildIndex] && this.heap[leftChildIndex] > this.heap[biggest] ) {
        biggest = leftChildIndex;
      }

      if ( this.heap[rightChildIndex] && this.heap[rightChildIndex] > this.heap[biggest] ) {
        biggest = rightChildIndex;
      }
      // 좌우 자식 모두 없는 경우
      if (biggest === index) break;

      this.swap(index, biggest);
      index = biggest;
    }
  }
}

function solution(n, works) {
    const sortedWorks = works.sort((a, b) => b - a);
    const len = sortedWorks.length;
    let answer = 0;
    const heap = new MaxHeap();
    
    for(let i = 0; i < len; i++){
        heap.push(sortedWorks[i]);
    }
    
    for(let i = 0; i < n; i++){
        let big = heap.pop();
        
        if(big === 0) return 0;
        heap.push(big - 1);
    }
    
    for(let i = 0; i < len; i++){
        answer += heap.pop() ** 2;
    }
    
    return answer;
}

 

그리디를 이용한 풀이

해당 문제에 대한 풀이중 최대힙을 사용하지 않은 풀이가 있어 한번 시도해 보았다.

 

이 풀이 방법 또한 표준편차를 줄인다는 목적은 같지만, 그리디 방식으로 접근했다. 

 

대략적인 흐름은 다음과 같다.

 

잔업 배열을 정렬한 뒤 n이 0보다 클때 동안 최대값과 각 요소들을 비교해 최대값보다 크거나 같을 경우 -1씩 더해주는 방법이다. 이때 -1을 더한다는 것은 잔업을 1 소화했다는 의미로 n에도 -1을 더해주어야 한다.

 

자세한 풀이 방법은 아래의 링크를 참고하면 좋겠다. 정말 잘 풀이되어있다.

[프로그래머스] LV.3 야근 지수 (JS)

 

 

코드

function solution(n, works) {
    const sortedWorks = works.sort((a, b) => b - a);
    const len = sortedWorks.length;
    let answer = 0;
    
    if(sortedWorks.reduce((acc, cur) => acc + cur, 0) <= n) return 0;
    
    while(n){
        for(let i = 0; i < len; i++){
            if(sortedWorks[i] >= sortedWorks[0]){
                n--;
                sortedWorks[i] -= 1;
            }
            if(!n){
                break;
            }
        }
    }
    
    return sortedWorks.reduce((acc, cur) => acc + cur ** 2, 0);
}