JavaScript로 정렬되지 않은 배열에서 최댓값과 최솟값 찾기

숫자로 이루어진 배열을 인자로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 선형 시간(O(n))과 상수 공간(O(1)) 안에서 배열에 존재하는 가장 큰 숫자와 가장 작은 숫자를 찾아야 하며, 최솟값(min)과 최댓값(max)을 포함하는 객체를 반환해야 합니다.

문제 접근 방법

배열을 오름차순으로 정렬한 뒤 첫 번째 요소와 마지막 요소를 가져오는 방법도 있지만, 정렬에는 일반적으로 O(n log n)의 시간이 소요되므로 요구 조건에 맞지 않습니다. 따라서 배열의 첫 번째 요소로 min과 max를 초기화하고, 배열을 단 한 번만 순회하면서 각 요소를 비교하여 값을 갱신하는 방식이 가장 효율적입니다.

예제

다음은 전체 코드입니다.

const arr = [112, 24, 31, 44, 101, 203, 33, 56];
const findMaxMin = (arr) => {
    let max = arr[0];
    let min = arr[0];
    for(let i = 0; i < arr.length; i++) {
       if(arr[i] > max) {
          max = arr[i];
       }
       else if (arr[i] < min) {
          min = arr[i];
       }
   };
   return {
      min, max
   };
};
console.log(findMaxMin(arr));

출력

다음은 콘솔에 출력된 결과입니다.

{ min: 24, max: 203 }

코드 설명

이 알고리즘은 배열의 첫 번째 요소로 min과 max를 초기화한 후, for 반복문으로 배열을 한 번 순회하면서 각 요소가 현재 max보다 크면 max를, 현재 min보다 작으면 min을 갱신합니다. if-else 구조를 사용하기 때문에 각 요소당 최대 두 번의 비교가 발생하지만, 전체적으로 배열을 한 번만 탐색하므로 시간 복잡도는 O(n)이며, 추가적인 자료구조를 사용하지 않으므로 공간 복잡도 역시 O(1)로 요구 사항을 모두 충족합니다.