자바스크립트 배열에서 n번째로 큰 값 찾기

09 Sep 2023

javascript

자바스크립트에서 배열에 저장된 값 중에서 n번째로 큰 값을 찾는 방법을 알아보겠습니다.

방법 1: 배열 정렬 후 인덱스로 찾기

가장 간단한 방법은 배열을 오름차순으로 정렬한 후, 인덱스를 이용하여 n번째로 큰 값을 찾는 것입니다. 아래 예제 코드를 통해 자세히 살펴보겠습니다.

function findNthLargest(arr, n) {
  arr.sort(function(a, b) {
    return b - a;
  });

  return arr[n - 1];
}

var numbers = [10, 5, 8, 2, 7];
var nthLargest = findNthLargest(numbers, 2);
console.log(nthLargest); // Output: 8

위의 코드에서는 findNthLargest 함수를 정의하였습니다. 이 함수는 입력으로 배열과 n 값을 받아서, 배열을 내림차순으로 정렬한 후 n번째 인덱스에 해당하는 값을 반환합니다.

예를 들어, 위의 코드에서는 numbers 배열에서 두 번째로 큰 값인 8을 찾고 있습니다.

방법 2: 우선순위 큐(Heap) 사용하기

또 다른 방법은 우선순위 큐(heap)를 사용하는 것입니다. 이 방법은 배열을 우선순위 큐로 다루어서 n번째로 큰 값을 찾는 것이 가능합니다. 아래 예제 코드를 통해 자세히 살펴보겠습니다.

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

  insert(value) {
    this.heap.push(value);
    this.bubbleUp();
  }

  bubbleUp() {
    let index = this.heap.length - 1;

    while (index > 0) {
      let element = this.heap[index];
      let parentIndex = Math.floor((index - 1) / 2);
      let parent = this.heap[parentIndex];

      if (parent >= element) {
        break;
      }

      this.heap[index] = parent;
      this.heap[parentIndex] = element;
      index = parentIndex;
    }
  }

  extractMax() {
    const max = this.heap[0];
    const last = this.heap.pop();

    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.bubbleDown();
    }

    return max;
  }

  bubbleDown() {
    let index = 0;

    while (true) {
      let leftChildIndex = 2 * index + 1;
      let rightChildIndex = 2 * index + 2;
      let swapIndex = null;

      if (leftChildIndex < this.heap.length) {
        if (this.heap[leftChildIndex] > this.heap[index]) {
          swapIndex = leftChildIndex;
        }
      }

      if (rightChildIndex < this.heap.length) {
        if (this.heap[rightChildIndex] > this.heap[swapIndex]) {
          swapIndex = rightChildIndex;
        }
      }

      if (swapIndex === null) {
        break;
      }

      let temp = this.heap[index];
      this.heap[index] = this.heap[swapIndex];
      this.heap[swapIndex] = temp;
      index = swapIndex;
    }
  }
}

function findNthLargest(arr, n) {
  let pq = new PriorityQueue();

  for (let i = 0; i < arr.length; i++) {
    pq.insert(arr[i]);

    if (pq.heap.length > n) {
      pq.extractMax();
    }
  }

  return pq.extractMax();
}

var numbers = [10, 5, 8, 2, 7];
var nthLargest = findNthLargest(numbers, 2);
console.log(nthLargest); // Output: 8

위의 코드에서는 먼저 PriorityQueue 클래스를 정의하고, 클래스 내부에서 우선순위 큐를 구현하였습니다. insert 메서드로 값들을 우선순위 큐에 삽입하고, extractMax 메서드로 가장 큰 값을 추출합니다.

findNthLargest 함수에서는 입력으로 받은 배열을 순회하면서 우선순위 큐에 값을 삽입하고, 큐의 크기가 n을 초과하면 가장 큰 값을 추출하여 크기를 조절합니다. 최종적으로 가장 큰 값을 추출하여 반환합니다.

이 방법은 배열이 커질수록 더욱 효율적인 성능을 보여줍니다.

결론

이상으로 자바스크립트 배열에서 n번째로 큰 값을 찾는 방법 두 가지에 대해 알아보았습니다. 각 방법마다 장단점이 있으니 상황에 맞게 선택하여 사용하면 됩니다. 감사합니다!