정렬 없이 JavaScript 배열에서 두 번째 최솟값 구하는 방법

숫자로 이루어진 배열이 주어졌을 때, 배열을 정렬하지 않고 두 번째로 작은 값을 반환하는 함수를 작성해야 하는 경우가 종종 있습니다. 이 글에서는 그 해결 방법을 단계별로 살펴보겠습니다.

문제 이해하기

예를 들어, 다음과 같은 배열이 있다고 가정해 보겠습니다:

const arr = [67, 87, 56, 8, 56, 78, 54, 67, 98, 56, 54];

이 배열에서 두 번째로 작은 값을 구하면 결과는 다음과 같아야 합니다:

54

그 이유는 배열에서 가장 작은 값이 8이고, 그다음으로 작은 값이 54이기 때문입니다.

접근 방법

배열을 정렬하지 않고 두 번째 최솟값을 구하는 핵심 아이디어는 다음과 같습니다:

1. Math.min()과 스프레드 연산자(...)를 활용해 배열 전체에서 최솟값을 찾습니다.
2. indexOf()로 해당 최솟값이 위치한 인덱스를 구합니다.
3. 원본 배열을 변경하지 않도록 복사본을 만든 뒤, 최솟값 하나를 제거합니다.
4. 최솟값이 제거된 배열에서 다시 최솟값을 찾으면, 그것이 곧 두 번째 최솟값입니다.

예제 코드

const arr = [67, 87, 56, 8, 56, 78, 54, 67, 98, 56, 54];

// 배열에서 최솟값의 인덱스를 반환하는 함수
const minimumIndex = arr => {
    return arr.indexOf(Math.min(...arr));
};

// 두 번째 최솟값을 반환하는 함수
const secondMinimum = arr => {
    const copy = arr.slice();            // 원본 배열 보호를 위해 복사본 생성
    copy.splice(minimumIndex(copy), 1);  // 최솟값 제거
    return copy[minimumIndex(copy)];     // 남은 값 중 최솟값 = 두 번째 최솟값
};

console.log(secondMinimum(arr));

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다:

54

코드 설명

• minimumIndex: Math.min(...arr)로 배열 전체의 최솟값을 구한 후, indexOf()를 통해 그 값이 위치한 인덱스를 반환합니다.
• secondMinimum: slice()를 사용해 원본 배열을 훼손하지 않고 복사본을 만든 뒤, splice()로 최솟값을 제거합니다. 이후 동일한 방식으로 다시 최솟값을 찾으면 자연스럽게 두 번째 최솟값이 됩니다.

이 방식은 최솟값 탐색을 두 번 수행하므로 전체 시간 복잡도가 O(n)입니다. 반면 배열을 정렬한 후 두 번째 요소를 가져오는 방식은 O(n log n)의 비용이 들기 때문에, 정렬 없이 접근하는 이 방법이 더 효율적이라 할 수 있습니다.