[백준] JavaScript - N번째 큰 수 (2075)

개요

문제 이름: N번째 큰 수 (2075)
문제 링크: https://www.acmicpc.net/problem/2075
플랫폼: 백준
알고리즘 분류: 정렬, 우선순위 큐
소요 시간: 3시간

 

문제 전문

설명

제한사항

메모리가 12 MB로 제한됨

입출력

 

문제 풀이

해설

이 문제는 우선순위 큐를 사용하여 N x N 크기의 표에 채워진 N^2개의 수 중에서 N번째로 큰 수를 찾는 문제입니다. 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 특징이 있으며, 표에 채워진 수는 모두 다릅니다. 그러기에 주어진 표에서 각 줄을 읽어 들이면서 현재 읽은 숫자들 중에서 N개의 가장 큰 수만 우선순위 큐에 유지하면 됩니다.

 

여기서 우선순위 큐는 우선순위가 가장 높은 요소를 먼저 꺼내는 자료구조입니다. 이 문제에서는 숫자가 클수록 우선순위가 높다고 가정하면, 우선순위 큐에 숫자를 삽입하고 크기가 N을 초과할 때마다 우선순위가 가장 낮은(가장 작은) 수를 제거하면서 N개의 최대값을 유지할 수 있습니다.

 

이를 위해 최소 힙(Min Heap)을 사용하면 편리합니다. 최소 힙은 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리 구조입니다. 최소 힙에서는 루트 노드에 가장 작은 값이 위치하고, 아래로 내려갈수록 값이 커집니다.

 

새로운 값을 삽입할 때는 일단 마지막 노드에 넣고 부모와 비교하면서 위치를 바꾸어 가며 적절한 위치를 찾아 올라갑니다. 최소값을 꺼낼 때는 루트 노드를 제거하고 마지막 노드를 루트로 가져와서 자식들과 비교하며 아래로 내려가며 적절한 위치를 찾습니다.

 

문제 풀이 과정을 자세히 설명하면 다음과 같습니다.

1. 먼저 입력값을 한 줄씩 읽어와야 합니다. 이때 readline 모듈을 사용하여 입력 스트림에서 데이터를 읽어올 수 있습니다. readline 모듈은 대용량 입력 데이터를 처리할 때 메모리 효율적입니다.
   1. readline의 경우 원래는 안 쓰려고 했는데 메모리 초과 때문에 반드시 써야 한다는 걸 알았습니다...
2. 첫 번째 줄에서는 표의 크기와 구해야 할 N번째 큰 수를 나타내는 N을 읽어옵니다.
3. 이후 N개의 줄에 걸쳐 표에 적힌 수를 읽어옵니다. 각 줄은 공백으로 구분된 N개의 수로 이루어져 있습니다.
4. 매 줄을 읽어올 때마다 해당 줄의 수들을 최소 힙에 삽입합니다.
   • 만약 최소 힙의 크기가 N보다 커진다면, 최소 힙에서 가장 작은 값(루트 노드)을 제거합니다.
   • 이렇게 하면 최소 힙에는 항상 지금까지 읽은 수 중에서 가장 큰 N개의 수만 남게 됩니다.
5. 모든 수를 읽고 처리한 후, 최소 힙의 루트 노드에 있는 값이 바로 N번째로 큰 수가 됩니다.

이 알고리즘의 핵심은 최소 힙을 사용하여 크기가 N인 우선순위 큐를 유지하는 것입니다. 매번 새로운 수를 읽을 때마다 최소 힙에 삽입하고, 힙의 크기가 N보다 커지면 가장 작은 값을 제거함으로써 항상 가장 큰 N개의 수만 유지할 수 있습니다. 이렇게 하면 전체 수를 정렬하지 않고도 효율적으로 N번째 큰 수를 찾을 수 있습니다.

 

문제 접근 방식을 정리하면 다음과 같습니다.

1. 최소 힙을 사용하여 크기가 N인 우선순위 큐를 유지합니다.
2. 입력값을 한 줄씩 읽어오면서 각 줄의 수들을 최소 힙에 삽입합니다.
3. 최소 힙의 크기가 N보다 커지면, 가장 작은 값을 제거합니다.
4. 모든 수를 처리한 후, 최소 힙의 루트 노드에 있는 값이 N번째 큰 수가 됩니다.

문제를 간략하게 요약하면 다음과 같습니다.

1. N x N 크기의 표에 수 N^2개가 채워져 있습니다.
2. 모든 수는 자신의 한 칸 위에 있는 수보다 큽니다.
3. 표에 채워진 수는 모두 다릅니다.
4. N번째로 큰 수를 찾아야 합니다.

 

우선순위 큐와 최소 힙

우선순위 큐

우선순위 큐는 일반적인 큐와 달리 우선순위에 따라 요소를 정렬하는 추상 자료형(ADT)입니다. 우선순위 큐에 요소를 삽입할 때는 우선순위를 함께 지정하며, 우선순위가 높은 요소가 먼저 제거됩니다. 우선순위 큐는 다음과 같은 두 가지 주요 연산을 지원합니다.

1. 삽입(Insert): 주어진 요소를 우선순위 큐에 추가합니다.
2. 최소값 삭제(Extract-Min) 또는 최대값 삭제(Extract-Max): 우선순위 큐에서 최소 또는 최대 우선순위를 가진 요소를 제거하고 반환합니다.

우선순위 큐는 운영체제의 작업 스케줄링, 네트워크 트래픽 제어, 그래프 알고리즘(최단 경로 알고리즘 등)에서 널리 사용되는 자료구조입니다. 우선순위 큐를 구현하는 대표적인 방법으로는 배열, 연결 리스트, 힙(Heap)이 있습니다. 이 중에서 힙을 사용한 구현이 가장 효율적입니다.

 

최소 힙

힙은 완전 이진 트리의 일종으로, 부모 노드와 자식 노드 간에 일정한 대소관계를 유지하는 자료구조입니다. 최소 힙(Min Heap)은 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같은 성질을 만족하는 힙입니다.

• 삽입 연산: 새로운 요소를 힙의 마지막 위치에 삽입한 후, 부모 노드와 비교하며 위로 올라가며 위치를 조정합니다. 이를 "업힙(Upheap)" 또는 "버블 업(Bubble-up)" 연산이라고 합니다.
• 최소값 삭제 연산: 힙에서 최소값(루트 노드)을 삭제한 후, 마지막 노드를 루트로 가져와 자식 노드들과 비교하며 아래로 내려가며 위치를 조정합니다. 이를 "다운힙(Downheap)" 또는 "버블 다운(Bubble-down)" 연산이라고 합니다.

최소 힙에서 삽입과 삭제 연산의 시간 복잡도는 O(log n)입니다. 최소 힙은 우선순위 큐를 효율적으로 구현하는 데 사용됩니다.

 

문제 해결에 최소 힙을 사용한 이유

이 문제에서는 N번째로 큰 수를 찾기 위해 우선순위 큐, 그 중에서도 최소 힙을 사용했습니다. 최소 힙을 사용한 이유는 다음과 같습니다.

1. 메모리 제한: 이 문제는 메모리 사용량이 12MB로 제한되어 있습니다. N의 최대값이 1,500이므로, 최대 1,500 x 1,500 = 2,250,000개의 숫자가 입력될 수도 있습니다. 만약 입력된 모든 숫자를 배열에 저장한 후 정렬한다면 메모리 제한을 초과할 가능성이 높습니다.
2. 효율성: 우선순위 큐를 사용하면 현재까지 입력된 숫자들 중에서 N개의 최대값만 유지할 수 있습니다. 새로운 숫자를 우선순위 큐에 삽입하고, 큐의 크기가 N을 초과하면 최소값을 삭제하는 방식으로 N개의 최대값을 유지할 수 있습니다. 이렇게 하면 모든 숫자를 저장할 필요 없이 문제를 해결할 수 있습니다.
3. 시간 복잡도: 힙을 사용한 우선순위 큐의 삽입과 삭제 연산은 O(log n)의 시간 복잡도를 가집니다. 따라서 N개의 최대값을 유지하는 데 효율적입니다.

이처럼 최소 힙을 사용한 우선순위 큐는 메모리 사용량을 최소화하면서도 효율적으로 N번째로 큰 수를 찾을 수 있는 방법입니다.

 

readline을 사용한 입력 처리

readline 모듈의 필요성

앞서 언급한 내용이지만, 이 문제에서는 입력 데이터의 크기가 최대 1,500 x 1,500 = 2,250,000개에 달할 수 있습니다. 즉, 이 문제에서 입력 데이터의 크기가 매우 크기 때문에, 일반적인 fs.readFileSync나 process.stdin.on('data', ...)를 사용하여 입력을 처리하면 메모리 제한을 초과할 가능성이 높습니다.

 

readline 모듈을 사용하면 입력 데이터를 한 줄씩 읽어올 수 있기 때문에 메모리 사용량을 줄일 수 있습니다. 이를 사용하면 입력 데이터를 한 번에 메모리에 올리지 않고, 한 줄씩 처리할 수 있습니다. 따라서 대용량 입력을 처리할 때 메모리 사용량을 크게 줄일 수 있습니다.

 

readline을 사용한 메모리 절약

readline 모듈을 사용하면 다음과 같은 방식으로 메모리를 절약할 수 있습니다.

1. 데이터를 한 줄씩 읽어들입니다. 따라서 전체 입력을 한 번에 메모리에 올릴 필요가 없습니다.
2. 읽어들인 한 줄의 데이터를 처리한 후에는 더 이상 필요하지 않으므로, 가비지 컬렉터에 의해 메모리에서 해제될 수 있습니다.
3. 이 문제에서는 매 줄을 읽어들인 후, 해당 줄의 숫자들을 우선순위 큐에 삽입하고, 큐의 크기가 N을 초과하면 최소값을 삭제합니다. 따라서 메모리에는 최대 N개의 숫자만 유지됩니다.

이처럼 readline 모듈을 사용하면 입력 데이터의 크기에 관계없이 메모리 사용량을 일정 수준으로 유지할 수 있습니다.

 

최적화 방법 요약

이 문제를 효율적으로 해결하기 위해 다음과 같은 최적화 기법을 사용할 수 있습니다.

1. 우선순위 큐(최소 힙)의 사용
   • N번째로 큰 수를 찾기 위해 우선순위 큐를 사용하여 현재까지 입력된 숫자들 중 N개의 최대값만 유지합니다.
   • 새로운 숫자를 우선순위 큐에 삽입하고, 큐의 크기가 N을 초과하면 최소값을 삭제하는 방식으로 N개의 최대값을 유지합니다.
   • 우선순위 큐의 삽입과 삭제 연산은 O(log n)의 시간 복잡도를 가지므로 효율적입니다.
2. readline 모듈을 사용한 입력 처리
   • 입력 데이터의 크기가 매우 크기 때문에, readline 모듈을 사용하여 데이터를 한 줄씩 읽어들입니다.
   • 한 줄씩 처리하므로 전체 입력을 한 번에 메모리에 올릴 필요가 없어 메모리 사용량을 크게 줄일 수 있습니다.
3. 불필요한 계산 최소화
   • 매 줄을 읽어들인 후, 해당 줄의 숫자들을 우선순위 큐에 삽입합니다.
   • 큐의 크기가 N을 초과할 때만 최소값을 삭제하므로, 불필요한 삭제 연산을 최소화합니다.
4. 공간 복잡도 최소화
   • 우선순위 큐에는 최대 N개의 숫자만 유지되므로, 메모리 사용량이 입력 데이터의 크기에 비해 매우 작습니다.
   • 입력 데이터를 한 줄씩 처리하므로, 전체 입력을 저장할 필요가 없어 메모리 사용량을 최소화할 수 있습니다.

 

시도

1차 시도  (성공)

// readline 모듈을 불러와 입력을 처리하기 위한 인터페이스를 설정
// 메모리를 효율적으로 사용하기 위해 readline 사용
const readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,    // 표준 입력 스트림 연결
    output: process.stdout   // 표준 출력 스트림 연결
});

/**
 * 최소 힙(Min Heap) 클래스
 * - 이진 힙 구조를 사용하여 최솟값을 빠르게 찾을 수 있게 구현
 * - 0번 인덱스는 null로 두어 인덱스 계산을 편리하게 함 (1부터 시작)
 * - 부모 노드의 인덱스 = Math.floor(현재 인덱스 / 2)
 * - 왼쪽 자식 노드의 인덱스 = 현재 인덱스 * 2
 * - 오른쪽 자식 노드의 인덱스 = 현재 인덱스 * 2 + 1
 */
class MinHeap {
    /**
     * 힙 초기화
     * - heap[0]은 null로 설정하여 인덱스 계산을 편리하게 함
     */
    constructor() {
        this.heap = [null];
    }

    /**
     * 새로운 값을 힙에 추가
     * - 값을 마지막에 추가한 후, 부모 노드와 비교하며 위로 올림(up-heap)
     * value = 힙에 추가할 값
     * 시간복잡도: O(log N)
     */
    push(value) {
        // 값을 힙의 마지막에 추가
        this.heap.push(value);
        // 추가된 값의 인덱스
        let currentIndex = this.heap.length - 1;

        // root(인덱스 1)에 도달하거나 부모 노드가 더 작을 때까지 반복
        while (currentIndex > 1) {
            // 현재 노드의 부모 노드 인덱스 계산
            const parentIndex = Math.floor(currentIndex / 2);
            // 부모 노드가 현재 노드보다 작거나 같으면 힙 속성 만족, 중단
            if (this.heap[parentIndex] <= this.heap[currentIndex]) break;

            // 부모 노드가 더 크면 위치 교환 (swap)
            [this.heap[parentIndex], this.heap[currentIndex]] = 
                [this.heap[currentIndex], this.heap[parentIndex]];
            // 현재 위치를 부모 노드 위치로 업데이트
            currentIndex = parentIndex;
        }
    }

    /**
     * 힙에서 최솟값을 제거하고 반환
     * - root 노드를 제거하고 마지막 노드를 root로 이동
     * - 자식 노드들과 비교하며 아래로 내림(down-heap)
     * 제거된 최솟값 또는 힙이 비어있는 경우 null
     * 시간복잡도: O(log N)
     */
    pop() {
        // 힙이 비어있으면 null 반환
        if (this.heap.length <= 1) return null;

        // root 값을 저장 (반환할 최솟값)
        const min = this.heap[1];
        // 마지막 노드를 root로 이동
        this.heap[1] = this.heap.pop();
        // 현재 비교할 노드의 인덱스
        let currentIndex = 1;

        while (true) {
            // 왼쪽, 오른쪽 자식 노드의 인덱스 계산
            const leftIndex = currentIndex * 2;
            const rightIndex = currentIndex * 2 + 1;
            // 현재까지 찾은 최소값의 인덱스
            let minIndex = currentIndex;

            // 왼쪽 자식이 존재하고 현재 최소값보다 작으면 minIndex 업데이트
            if (leftIndex < this.heap.length && 
                this.heap[leftIndex] < this.heap[minIndex]) {
                minIndex = leftIndex;
            }

            // 오른쪽 자식이 존재하고 현재 최소값보다 작으면 minIndex 업데이트
            if (rightIndex < this.heap.length && 
                this.heap[rightIndex] < this.heap[minIndex]) {
                minIndex = rightIndex;
            }

            // 자식 노드들이 현재 노드보다 크거나 같으면 힙 속성 만족, 중단
            if (minIndex === currentIndex) break;

            // 가장 작은 값을 가진 노드와 위치 교환 (swap)
            [this.heap[currentIndex], this.heap[minIndex]] = 
                [this.heap[minIndex], this.heap[currentIndex]];
            // 현재 위치를 업데이트
            currentIndex = minIndex;
        }

        return min;
    }

    /**
     * 현재 힙의 크기를 반환
     * 힙에 저장된 요소의 개수 (0번 인덱스 제외)
     * 시간복잡도: O(1)
     */
    size() {
        return this.heap.length - 1;
    }

    /**
     * 힙의 최솟값을 반환 (제거하지 않음)
     * 힙의 최솟값 (root 노드)
     * 시간복잡도: O(1)
     */
    peek() {
        return this.heap[1];
    }
}

// N: 표의 크기 및 구해야 할 N번째 큰 수의 N
// -1로 초기화하여 첫 입력을 N값으로 받을 것임을 표시
let N = -1;

// 상위 N개의 큰 수를 유지할 최소 힙 생성
const minHeap = new MinHeap();

// 입력 처리
rl.on("line", (line) => {
    // 첫 번째 입력인 경우 N 값을 설정
    if (N === -1) {
        N = parseInt(line);
        return;
    }

    // 각 줄의 입력을 공백으로 분리하여 처리
    line.split(" ").forEach((v) => {
        // 현재 수를 최소 힙에 추가
        minHeap.push(parseInt(v));
        // 힙의 크기가 N을 초과하면 최솟값 제거
        // 이렇게 하면 항상 상위 N개의 큰 수만 유지됨
        if (minHeap.size() > N) minHeap.pop();
    });

    // 한 줄 처리가 끝날 때마다 남은 줄 수 감소
    N--;
    // 모든 줄을 처리했으면 입력 종료
    if (N === 0) rl.close();
}).on("close", () => {
    // 최소 힙의 root가 N번째 큰 수
    // (힙에는 N개의 큰 수가 있고, 그 중 가장 작은 수가 N번째 큰 수)
    console.log(minHeap.peek());
    process.exit();
});

위 코드는 최소 힙을 구현하고, readline을 사용하여 입력을 처리하여 문제를 해결합니다.

1. readline 모듈을 사용하여 입력 스트림에서 데이터를 한 줄씩 읽어옵니다.
2. MinHeap 클래스를 구현하여 최소 힙 자료구조를 사용합니다.
   1. push 메서드는 새로운 값을 힙에 삽입하고, 힙의 속성을 유지하도록 노드를 재배치합니다.
   2. pop 메서드는 힙에서 가장 작은 값(루트 노드)을 제거하고 반환하며, 힙의 속성을 유지하도록 노드를 재배치합니다.
   3. size 메서드는 힙에 저장된 요소의 개수를 반환합니다.
   4. peek 메서드는 힙의 루트 노드(가장 작은 값)를 반환합니다.
3. rl.on("line", ...) 부분에서는 입력 스트림에서 한 줄씩 데이터를 읽어와 처리합니다.
   1. 첫 번째 줄에서는 N을 읽어와 저장합니다.
   2. 이후 N개의 줄에서는 각 줄의 수를 공백을 기준으로 분리하여 최소 힙에 삽입합니다.
   3. 최소 힙의 크기가 N보다 커지면 가장 작은 값(루트 노드)을 제거합니다.
   4. 입력 줄의 개수를 카운트하여 N이 0이 되면 입력 처리를 종료합니다.
4. rl.on("close", ...) 부분에서는 입력 처리가 완료된 후 최종 결과인 N번째 큰 수를 출력하고 프로그램을 종료합니다.

 

시간 복잡도 및 공간 복잡도

• 시간 복잡도: O(N^2 log N)
  • N개의 줄에 대해 각 줄마다 최대 N개의 숫자를 처리하므로 O(N^2)
  • 각 숫자마다 힙에 삽입 및 삭제 연산이 발생하며, 힙의 연산은 O(log N)이므로 총 O(N^2 log N)
• 공간 복잡도: O(N)
  • 힙의 크기가 최대 N까지 증가할 수 있으므로 O(N)의 추가 공간이 필요합니다.

 

사용된 주요 메서드

• Math.floor(x): 주어진 수 x를 내림한 값, 즉 x보다 작거나 같은 가장 큰 정수를 반환합니다.
• Array.prototype.push(...items): 배열의 끝에 하나 이상의 요소를 추가하고, 배열의 새로운 길이를 반환합니다.
• Array.prototype.pop(): 배열에서 마지막 요소를 제거하고 그 요소를 반환합니다.
• String.prototype.split(separator, limit): 문자열을 separator로 잘라서 limit 크기 이하의 배열에 잘라진 문자열을 저장하여 반환합니다.
• Array.prototype.forEach(callback): 배열의 각 요소에 대해 callback 함수를 실행합니다.
• parseInt(string, radix): 문자열을 radix 진수로 해석하고, 그 결과를 십진수의 정수로 반환합니다.