문제 소개
최소 한 쌍 이상의 중복된 숫자를 포함하는 숫자 배열을 입력으로 받아, 배열 안에 존재하는 모든 중복 숫자 쌍 사이의 거리(인덱스 차이)를 구하는 JavaScript 함수를 작성해야 합니다.
여기서 거리란 같은 숫자가 등장하는 인덱스 위치 간의 차이를 의미합니다. 숫자가 세 번 이상 등장하는 경우에는 인접한 등장 위치들 사이의 거리를 계산한 뒤, 그중 가장 작은 값을 결과로 삼는 방식이 효율적입니다.
해결 전략
이 문제는 다음과 같은 단계로 해결할 수 있습니다.
- 인덱스 매핑: 배열을 순회하면서 각 숫자가 등장한 인덱스들을 객체에 저장합니다.
- 중복 필터링: 두 번 이상 등장한 숫자만 골라냅니다.
- 거리 계산: 저장된 인덱스 목록에서 인접한 인덱스 간의 차이를 구하고, 그중 최솟값을 해당 숫자의 거리로 기록합니다.
구현 코드
const arr = [2, 3, 4, 2, 5, 4, 1, 3];
const findDistance = arr => {
var map = {}, res = {};
arr.forEach((el, ind) => {
map[el] = map[el] || [];
map[el].push(ind);
});
Object.keys(map).forEach(el => {
if (map[el].length > 1) {
res[el] = Math.min.apply(null, map[el].reduce((acc, val, ind, arr) => {
ind && acc.push(val - arr[ind - 1]);
return acc;
}, []));
};
});
return res;
}
console.log(findDistance(arr));
코드 상세 설명
핵심 로직을 단계별로 살펴보겠습니다.
- 인덱스 그룹화:
map객체에는 각 숫자를 키로, 해당 숫자가 등장한 인덱스 배열을 값으로 저장합니다. 예를 들어 숫자 2는 인덱스 0과 3에 위치하므로map[2]는[0, 3]이 됩니다. - 거리 산출:
reduce메서드가 인덱스 배열을 순회하며 현재 인덱스와 바로 앞 인덱스의 차이를 누적 배열에 추가합니다. 이렇게 하면 같은 숫자의 인접한 등장 위치 간 거리 목록이 만들어집니다. - 최솟값 선택:
Math.min.apply(null, ...)를 사용해 거리 목록 중 최솟값을 골라 결과 객체res에 저장합니다. - 중복 제외 처리: 한 번만 등장한 숫자는
map[el].length > 1조건에 걸려 결과에서 자동으로 제외됩니다.
실행 결과
위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.
{ '2': 3, '3': 6, '4': 3 }결과를 해석하면 다음과 같습니다.
- 숫자 2는 인덱스 0과 3에 있으므로 거리는 3입니다.
- 숫자 3은 인덱스 1과 7에 있으므로 거리는 6입니다.
- 숫자 4는 인덱스 2와 5에 있으므로 거리는 3입니다.
이처럼 객체를 활용해 인덱스를 그룹화하면 시간 복잡도 O(n)으로 배열을 한 번만 순회하면서도 모든 중복 숫자 간의 거리를 효율적으로 계산할 수 있습니다.