[JavaScript] 백준 11003 최솟값 찾기 (JS)

최솟값 찾기

📚 문제 설명

---

입력으로 N개의 수와 L이 주어진다.
D[i] = A[i] - L + 1 ~ A[i] 중의 최솟값이라고 할 때
D 배열을 출력하라.

👨🏻‍💻 풀이 과정

---

해당 문제는 이전에 사용했던 단조 스택과 유사한 풀이로 진행하면 된다.
적합한 자료구조(덱 or 우선순위 큐 or 배열)에 초기 입력 N개의 수를 삽입하며 확인하면 된다.

덱 Deque을 기준으로 설명하면 다음과 같다.

deque 정보

• deque[i]는 [ 값 , 인덱스 ] 가 저장된다.
• deque[0] 에는 가장 작은 값이 있다.

내부 메서드 로직

• PushBack(e) 메서드를 실행하면 덱이 무조건 오름차순이 되도록 넣는다.
  • deque[deque.length - 1]이 e보다 크면 pop().
  • 위의 조건 반복.
• Min(i)를 통해 찾아야하는 배열인 D[i]를 찾는다.
  • deque[0][1] 은 앞서 말했듯 초기 배열에서의 인덱스 값이다.
  • 따라서 deque[0][1]이 i - L보다 작거나 같으면 PopFront().

이제 메인 로직을 살펴보면 다음과 같다.

M : 문제에서 주어지는 L 값.
input : N개의 입력 배열

• input을 하나씩 순회하며 deque에 PushBack.
• Min(i)를 하여 D[i]를 찾아 정답에 추가.

💡덱(Deque) 사용

PushFront 메서드의 경우 덱을 구현하며 초기에 구현한 코드인데 사용되지 않기 때문에 무시하셔도 좋을 것 같습니다.

let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");

const [N, M] = input.shift().split(' ').map(Number);
input = input.shift().split(' ').map(Number);

class Node {
    constructor(value, index) {
        this.value = value;
        this.index = index;
        this.prev = null;
        this.next = null;
    }
}

class Deque {
    constructor(l) {
        this.head = null;
        this.tail = this.head;
        this.L = l;
        this.length = 0;
    }

    PushFront(value, index) {
        const insertNode = new Node(value, index);
        if (this.length === 0) {
            this.tail = insertNode;
        } else {
            this.head.prev = insertNode;
            insertNode.next = this.head;
        }
        this.head = insertNode;
        this.length++;
    }

    PushBack(value, index) {
        const insertNode = new Node(value, index);

        while (this.tail) {
            if (this.tail.value > value) {
                this.PopBack();
            } else break;
        }

        if (this.length === 0) {
            this.head = insertNode;
        } else {
            this.tail.next = insertNode;
            insertNode.prev = this.tail;
        }
        this.tail = insertNode;
        this.length++;
    }

    PopFront() {
        if (this.length === 0) return null;

        const value = this.head.value;
        if (this.length === 1) {
            this.head = null;
            this.tail = null;
        } else {
            const prevHead = this.head;
            this.head = prevHead.next;
            this.head.prev = null;
            prevHead.next = null;
        }
        this.length--;
        return value;
    }

    PopBack() {
        if (this.length === 0) return null;

        const value = this.tail.value;
        if (this.length === 1) {
            this.head = null;
            this.tail = null;
        } else {
            const prevTail = this.tail;
            this.tail = prevTail.prev;
            this.tail.next = null;
            prevTail.prev = null;
        }
        this.length--;
        return value;
    }

    GetMin(now) {
        while (this.head) {
            if (this.head.index <= now - this.L) {
                this.PopFront();
            } else break;
        }
        return this.head.value;
    }
}

const deque = new Deque(M);
let result = '';

for (let i = 0; i < input.length; i++) {
    deque.PushBack(input[i], i);

    if (i > 0) {
        result += ' ';
    }
    result += deque.GetMin(i);

    if (i % 10000 === 0) {
        process.stdout.write(result);
        result = '';
    }
}

console.log(result);

💡우선순위 큐(Priority Queue) 사용

let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");
const [N, M] = input.shift().split(' ').map(v => +v);
input = input[0].split(' ').map(v => +v);

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

    Insert(value, index) {
        let cur = this.queue.length;
        while (cur > 1) {
            const parent = Math.floor(cur / 2);
            if (this.queue[parent][0] > value) {
                this.queue[cur] = this.queue[parent];
                cur = parent;
            } else break;
        }
        this.queue[cur] = [value, index];
    }

    Pop() {
        if (this.queue.length > 2) {
            const popElement = this.queue[1];
            this.queue[1] = this.queue.pop();

            let cur = 1;
            let left = cur * 2;
            let right = cur * 2 + 1;

            while (this.queue[left]) {
                let compare = left;
                if (this.queue[right] && this.queue[left][0] > this.queue[right][0]) {
                    compare = right;
                }
                if (this.queue[compare][0] < this.queue[cur][0]) {
                    [this.queue[cur], this.queue[compare]] = [this.queue[compare], this.queue[cur]];
                    cur = compare;
                    left = cur * 2;
                    right = cur * 2 + 1;
                } else break;
            }
            return popElement;
        } else if (this.queue.length === 2) {
            return this.queue.pop();
        } else {
            return null;
        }
    }

    Min(now) {
        if (this.queue.length < 2) return null;

        while (this.queue.length > 1 && this.queue[1][1] < now - this.M + 1) {
            this.Pop();
        }

        return this.queue.length > 1 ? this.queue[1] : null;
    }
}

const pq = new MinHeap(M);
let result = '';

for (let i = 0; i < input.length; i++) {
    pq.Insert(input[i], i);

    if (i > 0) {
        result += ' ';
    }
    result += pq.Min(i)[0];

    if (i % 10000 === 0) {
        process.stdout.write(result);
        result = '';
    }
}

console.log(result);

💡배열 사용

배열을 이용한 코드는 다른 분들의 코드를 참고했습니다.

let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");

const [N, L] = input.shift().split(' ').map(Number);
const arr = input.shift().split(' ').map(Number);

// 덱을 배열로 구현하되 투 포인터 방식 사용
const deque = new Array(N); // 미리 할당
let front = 0; // 앞쪽 포인터
let rear = 0;  // 뒤쪽 포인터

let result = ""; // 배열 대신 문자열 사용

for (let i = 0; i < N; i++) {
    // 현재 윈도우 범위를 벗어난 인덱스들 제거
    while (front < rear && deque[front] < i - L + 1) {
        front++; // shift() 대신 포인터만 이동
    }

    // 현재 값보다 큰 값들을 뒤에서부터 제거 (단조 덱 유지)
    while (front < rear && arr[deque[rear - 1]] >= arr[i]) {
        rear--; // pop() 대신 포인터만 이동
    }

    // 현재 인덱스 추가
    deque[rear] = i;
    rear++;

    // 덱의 첫 번째 인덱스가 현재 윈도우의 최솟값
    if (i === 0) {
        result = arr[deque[front]].toString();
    } else {
        result += " " + arr[deque[front]];
    }
}

console.log(result);

---

🚨 주의 사항

위의 코드들을 보면 공통적으로 이해할 수 없는 로직이 들어있는 것을 볼 수 있다.
마지막 결과 출력 부분을 살펴보면 process.stdout.write를 통해 결과를 끊어서 입력하는 것이 보인다.

만약 이렇게 입력을 끊어서 출력하지 않을 경우 아래와 같이
우선순위 큐를 사용하든 덱을 사용하든 메모리 초과가 발생한다.

해당 문제를 해결하기 위해 다양한 방법을 시도하던 중 한 게시글을 보게 되었다.

요약하면 결과 배열을 한번에 문자열로 출력하면 메모리 초과가 발생하기 때문에
process write를 이용해 정답 배열을 끊어서 출력해야 한다는 것이다.

따라서 다음과 같이 일정 단위로 정답 문자열을 입력시키고 정답 배열을 초기화시키는 최적화가 필요하다.

 if (i % 10000 === 0) {
        process.stdout.write(result);
        result = '';
    }

🧐 후기

---

아무리 해도 메모리 초과가 발생하여 너무 힘들었던 문제였다.
질문 게시판에 node js 관련 글이 없었다면 끝까지 문제 원인을 찾지 못했을 것 같다.
이렇게 출력을 끊어서 진행해야하는 문제는 처음 겪어서 당황했고 문제를 분석하기 위해 덱을 연결리스트가 아닌 배열로 구현하는 방법, 배열의 크기를 미리 할당하는 방법 등 다양한 고민을 해볼 수 있었던 점에서는 좋았던 것 같다.