1781 컵라면 (자바스크립트 / 파이썬)

문제

상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라인을 정하였다.

문제 번호데드라인컵라면 수

1	2	3	4	5	6	7
1	1	3	3	2	2	6
6	7	2	1	4	5	1

위와 같은 상황에서 동호가 2, 6, 3, 1, 7, 5, 4 순으로 숙제를 한다면 2, 6, 3, 7번 문제를 시간 내에 풀어 총 15개의 컵라면을 받을 수 있다.

문제는 동호가 받을 수 있는 최대 컵라면 수를 구하는 것이다. 위의 예에서는 15가 최대이다.

문제를 푸는데는 단위 시간 1이 걸리며, 각 문제의 데드라인은 N이하의 자연수이다. 또, 각 문제를 풀 때 받을 수 있는 컵라면 수와 최대로 받을 수 있는 컵라면 수는 모두 231보다 작은 자연수이다.

입력

첫 줄에 숙제의 개수 N (1 ≤ N ≤ 200,000)이 들어온다. 다음 줄부터 N+1번째 줄까지 i+1번째 줄에 i번째 문제에 대한 데드라인과 풀면 받을 수 있는 컵라면 수가 공백으로 구분되어 입력된다.

출력

첫 줄에 동호가 받을 수 있는 최대 컵라면 수를 출력한다.

 

=====

문제 풀이 

이 문제는 최소 힙큐를 사용해서 풀거나 이진탐색 알고리즘을 활용해서 풀 수있다.

1. 최소 힙큐 

1) 우선 입력값을 데드라인을 기준으로 오름차순 정렬한다.

2) 최소 힙큐를 생성한 뒤에 입력값의 배열을 탐색한다.

3) 배열 엘리먼트의 데드라인이 힙큐의 사이즈보다 크다면 힙큐에 라멘 갯수를 삽입해준다.

4) 만약 데드라인이 힙큐의 사이즈보다 작다면 힙큐에서 값을 하나 pop(제일 작은 값) 하여 지금의 라멘과 비교한 뒤에 더 큰값을 힙큐에 삽입해준다. 

5) 힙큐에 담긴 라멘의 합을 출력한다. 

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

    push(arr) {
        this.heap.push(arr);
        let idx = this.heap.length - 1;
        while (idx > 1) {
            let parent = Math.floor(idx / 2);
            if (this.heap[parent][0] < this.heap[idx][0]) break;
            else {
                [this.heap[parent], this.heap[idx]] = [
                    this.heap[idx],
                    this.heap[parent],
                ];
                idx = parent;
            }
        }
    }

    pop() {
        if (this.heap.length === 1) return undefined;
        const min = this.heap[1];
        const last = this.heap.pop();
        if (this.heap.length === 1) return min;
        this.heap[1] = last;

        let idx = 1;
        while (true) {
            let left = idx * 2;
            let right = idx * 2 + 1;
            let smallest = idx;

            if (left < this.heap.length) {
                if (this.heap[left][0] < this.heap[smallest][0]) {
                    smallest = left;
                }
            }
            if (right < this.heap.length) {
                if (this.heap[right][0] < this.heap[smallest][0]) {
                    smallest = right;
                }
            }
            if (smallest === idx) break;
            [this.heap[idx], this.heap[smallest]] = [
                this.heap[smallest],
                this.heap[idx],
            ];
            idx = smallest;
        }

        return min;
    }

    isEmpty() {
        return this.heap.length === 1;
    }
    size() {
        return this.heap.length - 1;
    }
    result() {
        return this.heap.slice(1).reduce((acc, cur) => acc + cur[0], 0n);
    }
}
const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const n = +input[0];
const arr = input
    .slice(1)
    .map((s) => s.split(' ').map(Number))
    .map((v) => {
        return {
            deadline: v[0],
            ramen: BigInt(v[1]),
        };
    })
    .sort((a, b) => a.deadline - b.deadline);

const hq = new MinHeap();

for (const { ramen, deadline } of arr) {
    if (hq.isEmpty()) {
        hq.push([ramen]);
        continue;
    }
    if (hq.size() < deadline) {
        hq.push([ramen]);
    } else {
        const [r] = hq.pop();
        const large = r > ramen ? r : ramen;
        hq.push([large]);
    }
}

console.log(hq.result().toString());

 

2. 이진 탐색 알고리즘

위의 방식과 동일하지만 힙큐에서 작은 값을 pop하여 비교하는 대신 빈 배열에 이진탐색을 통해 알맞은 위치에 넣어준다. 이때 배열은 오름차순으로 정렬이 되어야한다. 만약 배열의 사이즈가 현재의 데드라인보다 크다면 첫번째 값을 pop해주는 것으로 균형을 맞추면 된다.

이 코드는 파이썬으로 bisect 활용함.

import sys
import bisect

input = sys.stdin.read
data = input().strip().split('\n')

n = int(data[0])
arr = []

for line in data[1:]:
    d, r = map(int, line.split())
    arr.append((d, r))

arr.sort()

stack = []

for deadline, ramen in arr:
    bisect.insort(stack, ramen)
    if len(stack) > deadline:
        stack.pop(0)

print(sum(stack))