글 읽기 - node에서 왜 메모리초과가 나는지 모르겠습니다

jungsangu 1년 전 0

nodejs에서 계속 메모리 초과가 납니다.

답은 정상적으로 나오는데

어떤 부분에서 메모리 초과가 나는지 모르겠습니다.

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').slice(1);

class MinHeap {
    constructor() {
        this.arr = [Number.MIN_SAFE_INTEGER];
    }
    
    empty() {
        return this.arr.length === 1;
    }
    top() {
        return this.arr[1];
    }

    insert(n) {
        const arr = this.arr;
        arr.push(n)
        for (let i = arr.length - 1; arr[i] < arr[Math.floor(i / 2)]; i = Math.floor(i / 2)) {
            [arr[i], arr[Math.floor(i / 2)]] = [arr[Math.floor(i / 2)], arr[i]];
        }
    }

    remove() {
        const arr = this.arr;
        const root = arr[1];
        
        if (arr.length === 1) {
            return undefined;
        }
        if (arr.length === 2) {
            return arr.pop();
        }

        arr[1] = arr.pop();

        for (let i = 1; arr[i] > arr[i * 2] || arr[i] > arr[i * 2 + 1];) {
            if (arr[i * 2 + 1] === undefined || arr[i * 2] < arr[i * 2 + 1]) {
                [arr[i], arr[i * 2]] = [arr[i * 2], arr[i]];
                i = i * 2;
            } else {
                [arr[i], arr[i * 2 + 1]] = [arr[i * 2 + 1], arr[i]];
                i = i * 2 + 1;
            }
        }

        return root;
    }
}

class MaxHeap {
    constructor() {
        this.arr = [Number.MAX_SAFE_INTEGER];
    }

    empty() {
        return this.arr.length === 1;
    }
    top() {
        return this.arr[1];
    }
    
    insert(n) {
        const arr = this.arr;
        arr.push(n)
        for (let i = arr.length - 1; arr[i] > arr[Math.floor(i / 2)]; i = Math.floor(i / 2)) {
            [arr[i], arr[Math.floor(i / 2)]] = [arr[Math.floor(i / 2)], arr[i]];
        }
    }

    remove() {
        const arr = this.arr;
        const root = arr[1];
        
        if (arr.length === 1) {
            return undefined;
        }
        if (arr.length === 2) {
            return arr.pop();
        }

        arr[1] = arr.pop();

        for (let i = 1; arr[i] < arr[i * 2] || arr[i] < arr[i * 2 + 1];) {
            if (arr[i * 2 + 1] === undefined || arr[i * 2] > arr[i * 2 + 1]) {
                [arr[i], arr[i * 2]] = [arr[i * 2], arr[i]];
                i = i * 2;
            } else {
                [arr[i], arr[i * 2 + 1]] = [arr[i * 2 + 1], arr[i]];
                i = i * 2 + 1;s
            }
        }

        return root;
    }
}

for (let i = 0; i < input.length;) {
    const minH = new MinHeap();
    const maxH = new MaxHeap();
    const map = {};
    const T = Number(input[i]);
    for (let j = i + 1; j < i + 1 + T; j += 1) {
        let [ch, n] = input[j].split(' ');
        n = Number(n);

        if (ch === 'I') {
            minH.insert(n);
            maxH.insert(n);
            map[n] = (map[n]) ? map[n] + 1 : 1;
        } else {
            if (n === 1) {
                while (!maxH.empty()) {
                    const max = maxH.remove();
                    if (map[max] > 0) {
                        map[max] -= 1;
                        break;
                    }
                }
            } else {
                while (!minH.empty()) {
                    const min = minH.remove();
                    if (map[min] > 0) {
                        map[min] -= 1;
                        break;
                    }
                }
            }
        }
    }

    while (!minH.empty() && !(map[minH.top()] > 0)) {
        minH.remove();
    }
    while (!maxH.empty() && !(map[maxH.top()] > 0)) {
        maxH.remove();
    }

    if (minH.empty() || maxH.empty()) {
        console.log('EMPTY')
    } else {
        console.log(maxH.top(), minH.top());
    }

    i += T + 1;
}

mike0022 4달 전 0

안녕하세요, 저도 아직 문제를 푸는 중인데요, input을 받으실 때 readline을 통해서 한 줄씩 받는 것으로 시도해보심이 어떨까요? 케이스 별로 최대 명령 수가 백만개여서, 케이스가 많은 경우에는 input배열이 엄청 커질 것 같다는 생각이 들었습니다.

실제로 저는 readline으로 변경하여 한 줄 마다 처리를 하게 코드를 변경했더니 메모리초과는 벗어나더라구요 ㅎㅎ 그치만 저는 시간초과에 걸려서...조금 더 생각해봐야할 것 같아요ㅜㅜ

제 첨언과는 별개로, 첨부해주신 코드에서 map을 활용하셨는데, 이 부분에서 제 코드의 시간복잡도를 개선할 수 있는 힌트를 얻었습니다. 감사합니다!

그럼 화이팅입니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

node에서 왜 메모리초과가 나는지 모르겠습니다

jungsangu 1년 전 0

mike0022 4달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말