JavaScript에서 값이 증가할 때 가장 큰 인덱스 차이 구하는 방법

문제 설명

숫자로 이루어진 배열 arr을 입력받는 JavaScript 함수를 작성해야 합니다. 이 함수는 arr[i] <= arr[j] 조건을 만족하는 모든 인덱스 쌍 중에서, 인덱스 차이 j - i가 가장 큰 값을 반환해야 합니다.

즉, 뒤에 있는 요소가 앞에 있는 요소보다 크거나 같을 때 두 인덱스 사이의 거리가 최대한 멀어지는 경우를 찾는 것입니다.

접근 방법

가장 직관적인 해결 방법은 이중 반복문을 활용하는 것입니다. 바깥쪽 반복문으로 시작 인덱스 i를 순회하고, 안쪽 반복문으로 비교 인덱스 j를 순회하면서 조건을 만족하는 경우마다 인덱스 차이를 갱신합니다. 시간 복잡도는 O(n²)이지만, 문제의 의도를 명확하게 이해하기 좋은 방식입니다.

구현 코드

이를 구현한 코드는 다음과 같습니다.

const arr = [1, 2, 3, 4];

const findLargestDifference = (arr = []) => {
    const { length: len } = arr;
    let res = 0;

    for(let i = 0; i < len; i++){
        for(let j = i + 1; j < len; j++){
            if(arr[i] <= arr[j] && (j - i) > res){
                res = j - i;
            }
        }
    }

    return res;
};

console.log(findLargestDifference(arr));

실행 결과

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

3

동작 원리 분석

위 예제에서 배열은 [1, 2, 3, 4]로 오름차순 정렬되어 있습니다. 따라서 i = 0, j = 3일 때 arr[0] <= arr[3](1 ≤ 4) 조건을 만족하며, 이때 인덱스 차이 3 - 0 = 3이 최대값이 됩니다.

코드의 주요 흐름은 다음과 같습니다.

• 결과값 res를 0으로 초기화합니다.
• 바깥쪽 반복문으로 각 시작 인덱스 i를 확인합니다.
• 안쪽 반복문에서 j를 i + 1부터 끝까지 탐색하며 arr[i] <= arr[j]를 검사합니다.
• 조건을 만족하고 기존 결과보다 더 큰 인덱스 차이라면 res를 갱신합니다.

만약 배열이 내림차순으로 정렬된 경우처럼 조건을 만족하는 쌍이 하나도 없다면, 초기값인 0이 그대로 반환됩니다.