JavaScript로 두 배열에서 인덱스 합이 가장 작은 공통 요소 찾기

문제 설명

두 개의 배열 arr1과 arr2를 각각 첫 번째, 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다.

함수는 두 배열에 공통으로 존재하는 요소 중 리스트 인덱스 합(list index sum)이 가장 작은 요소를 찾아 반환해야 합니다. 만약 조건을 만족하는 요소가 여러 개라면(동률인 경우) 순서에 상관없이 모두 출력하면 됩니다.

예를 들어, 함수의 입력이 다음과 같다고 가정해 보겠습니다.

const arr1 = ['a', 'b', 'c', 'd'];
const arr2 = ['d', 'a', 'c'];

그렇다면 출력 결과는 다음과 같아야 합니다.

const output = ['a'];

출력 설명

'd'와 'a'는 두 배열 모두에 존재하는 공통 요소입니다. 'd'의 인덱스 합은 3 + 0 = 3이고, 'a'의 인덱스 합은 0 + 1 = 1입니다. 따라서 인덱스 합이 더 작은 'a'가 정답이 됩니다.

코드 구현

다음은 이 문제를 해결하는 전체 코드입니다.

const arr1 = ['a', 'b', 'c', 'd'];
const arr2 = ['d', 'a', 'c'];
const findCommon = (arr1 = [], arr2 = []) => {
    let sum = Infinity
    const map = arr1.reduce((acc, str, index) => {
        acc[str] = index
        return acc
    }, {})
    for (let i = 0; i < arr2.length; i++) {
        const index1 = map[arr2[i]]
        if (index1 >= 0 && index1 + i < sum) {
            sum = index1 + i
        }
    }
    const result = []
    for (let i = 0; i < arr2.length; i++) {
        const index1 = map[arr2[i]]
        if (index1 >= 0 && index1 + i === sum) {
            result.push(arr2[i])
        }
    }
    return result
}
console.log(findCommon(arr1, arr2));

출력 결과

콘솔에는 다음과 같이 출력됩니다.

['a']

동작 원리

이 코드의 핵심 로직은 다음 세 단계로 구성됩니다.

인덱스 맵 생성: reduce() 메서드를 사용해 arr1의 각 요소를 키로, 해당 인덱스를 값으로 하는 객체(map)를 만듭니다. 이를 통해 특정 요소의 인덱스를 O(1) 시간에 조회할 수 있습니다.
최소 인덱스 합 계산: 첫 번째 반복문에서 arr2의 각 요소가 맵에 존재하는지 확인하고, 존재한다면 두 배열에서의 인덱스 합을 계산하여 기존 최솟값(sum)보다 작으면 갱신합니다.
정답 수집: 두 번째 반복문에서 인덱스 합이 최솟값과 정확히 일치하는 모든 공통 요소를 결과 배열에 추가합니다. 이 과정 덕분에 동률인 경우에도 여러 개의 정답을 모두 반환할 수 있습니다.

이 알고리즘의 시간 복잡도는 O(n + m)으로, 두 배열의 길이에 비례하여 선형적으로 증가하므로 효율적입니다.