[JavaScript] 백준 1781 컵라면 (JS)

컵라면

📚 문제 설명

---

N 개의 문제가 주어지고 각각에 문제에는 데드라인과, 데드라인 안에 풀었을 때 보상으로 얻게 되는 컵라면의 갯수가 있다.
여기서 내가 데드라인 안에 어떤 문제들을 풀어야 컵라면을 최대로 얻을 수 있을까?
(단, 문제를 푸는데 1의 시간이 걸린다.)

문제 번호	1	2	3
데드 라인	1	1	3
컵라면 수	6	7	2

예를 들어 다음과 같이 입력이 주어질 때, 컵라면을 가장 많이 먹으면 몇개를 먹을 수 있을까?

만약 1 - 2 - 3 순서대로 풀게 된다면, 문제 각각 6, 0, 2 개의 컵라면을 얻을 수 있기 때문에 총 8개의 컵라면을 얻을 수 있다.
그러나 만약 2 - 1 - 3 순서로 푼다면, 각각 0, 7, 2 개의 컴라면을 얻을 수 있기 때문에 총 9개를 얻을 수 있고, 이때가 최대가 된다.

👨🏻‍💻 풀이 과정

---

이 문제에서 최대 값은 아마 각각의 데드라인에 컵라면이 가장 많은 값만 가져와 합했을 때일 것이다.
그럼 각각의 데드라인의 컵라면 최대 값을 어떻게 가져올까?

• 우선 입력에서 DeadLine 을 기준으로 오름차순 정렬을 해줬다.
• 그 후 최소 우선 순위 큐 MinHeap 를 만들었다.
• MinHeap의 길이 GetLength() 는 DeadLine 을 의미한다. 따라서 만약 문제의 DeadLine 이 우선순위 큐의 길이GetLength() 와 같다면 CupNoodle 과 MinHeap 최상단GetTop()과 비교한다.
• 비교후 Pop , Insert() 진행.

위 과정의 핵심은 미리 DeadLine 기준으로 오름차순 정렬한 배열을 MinHeap과 하나씩 비교한다는 것과
데드라인이 1일 때는 1문제를 풀 수 있고, 2일 때는 2문제를 풀수 있다는 것.
우선 순위 큐의 길이 = 데드라인.
라고 생각하면 이해가 쉬울 것이다.

메인 로직 코드

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const N = input.shift();

input = input.map(v => v.split(' ').map(Number)).sort((a, b) => a[0] - b[0]);
let answer = 0;

class MINHEAP {
	//생략
}

const solution = (INPUT) => {
    const MinHeap = new MINHEAP();
    for (const inputElement of INPUT) {
        let [DeadLine, CupNoodle] = inputElement;
		// 만약 다음 문제 데드라인과 지금까지 푼 문제의 수가 같다면
        if (DeadLine === MinHeap.GetLength()) {
          // 우선순위큐를 통해 가장 작은 값 교체
            if (MinHeap.GetTop() < CupNoodle) {
                MinHeap.Pop();
                MinHeap.Insert(CupNoodle);
            }
        } else {
            MinHeap.Insert(CupNoodle);
        }
    }
    console.log(MinHeap.GetSum());
};
solution(input);

우선 순위 큐의 경우 바로 이전에 풀었던 문제의 우선 순위 큐 코드를 그대로 재사용했다.
그렇게 우선 순위 큐를 포함한 전체 코드는 다음과 같다.

전체 코드

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    const N = input.shift();

    input = input.map(v => v.split(' ').map(Number)).sort((a, b) => a[0] - b[0]);
    let answer = 0;

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

        Insert(item) {
            let cur = this.heap.length;
            while (cur > 1) {
                const parent = Math.floor(cur / 2);
                if (this.heap[parent] > item) {
                    this.heap[cur] = this.heap[parent];
                    cur = parent
                }else break;
            }
            this.heap[cur] = item;
        }

        Pop(){
            const PopItem = this.heap[1];
            if (this.heap.length > 2) {
                this.heap[1] = this.heap.pop();
                let Current = 1;
                let LeftChild = Current * 2;
                let RightChild = Current * 2 + 1;
                while (this.heap[LeftChild]) {
                    let ComparedChild = LeftChild;
                    if (this.heap[RightChild] && this.heap[LeftChild] > this.heap[RightChild]) {
                        ComparedChild = RightChild;
                    }

                    if (this.heap[Current] > this.heap[ComparedChild]) {
                        [this.heap[Current], this.heap[ComparedChild]] = [this.heap[ComparedChild], this.heap[Current]];
                    }else break;
                    Current = ComparedChild;
                    LeftChild = Current * 2;
                    RightChild = Current * 2 + 1;
                }
            }else if (this.heap.length === 2) {
                this.heap.pop();
                return PopItem;
            } else {
                return null;
            }
            return PopItem;
        }

        GetLength() {
            return this.heap.length - 1;
        }

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

        GetSum() {
            let sum = 0;
            for (let i = 1; i < this.heap.length; i++) {
                sum += this.heap[i];
            }
            return sum;
        }
    }

    const solution = (INPUT) => {
        const MinHeap = new MINHEAP();
        for (const inputElement of INPUT) {
            let [DeadLine, CupNoodle] = inputElement;

            if (DeadLine === MinHeap.GetLength()) {
                if (MinHeap.GetTop() < CupNoodle) {
                    MinHeap.Pop();
                    MinHeap.Insert(CupNoodle);
                }
            } else {
                MinHeap.Insert(CupNoodle);
            }
        }
        console.log(MinHeap.GetSum());
    };
    solution(input);

🧐 후기

---

sort를 하면 시간 초과가 날 것 같다는 생각에 sort를 너무 배제하고 생각했던 것 때문에 사고가 좀 닫혔던 것 같다.
그리고 해당 문제에서 우선 순위 큐의 길이를 이용하여 풀었는데 미처 생각해내질 못했다. 아직 우선 순위 큐를 완벽하게 활용하지 못하는 것 같다.