JavaScript 배열에서 중복 값의 무작위 인덱스 선택하기

문제 상황

JavaScript로 다음과 같은 함수를 작성해야 합니다.

첫 번째 인수로 숫자 배열 arr을 받습니다. 이 배열에는 중복된 값이 포함될 수 있습니다. 두 번째 인수로는 배열에 실제로 존재하는 정수 하나를 받습니다.

함수는 해당 숫자가 배열에 존재하는 인덱스를 반환해야 합니다. 단, 그 숫자가 배열에 여러 번 등장할 수 있기 때문에, 가능한 인덱스들 중에서 무작위로 하나를 골라 반환해야 합니다.

입력 예시

const arr = [5, 3, 6, 7, 3, 4, 2, 3];
const num = 3;

출력 예시

const output = 4;

출력 설명

숫자 3은 배열에서 인덱스 1, 4, 7에 위치하고 있습니다. 인덱스를 무작위로 선택해야 하므로 출력은 1, 4, 7 중 어느 것이든 나올 수 있습니다. 이번 실행에서는 4가 선택된 것입니다.

구현 코드

이 문제를 해결하는 코드는 다음과 같습니다. 재귀적으로 배열을 분할하며 목표 값을 찾은 뒤, 찾은 인덱스들을 모아 무작위로 하나를 반환하는 방식입니다.

const arr = [5, 3, 6, 7, 3, 4, 2, 3];
const num = 3;
Array.prototype.pick = function(target) {
   const targets = []
   this.findTarget(0, this.length, target, targets);
   return targets[Math.floor(Math.random() * targets.length)];
};
Array.prototype.findTarget = function(start, end, target, targets) {
   if(start + 1 === end || start === end) {
      if(this[start] === target) targets.push(start);
      return;
   }
   let j = start + Math.floor((end - start)/2);
   this.findTarget(start, j, target, targets);
   this.findTarget(j, end, target, targets);
};
console.log(arr.pick(num));

코드 동작 원리

pick 메서드는 먼저 빈 배열 targets를 생성한 후, findTarget을 호출해 배열 전체(0부터 length까지)를 탐색합니다.

findTarget은 배열을 절반씩 나누어 재귀적으로 탐색합니다. 구간이 더 이상 나눌 수 없을 만큼 작아지면(start + 1 === end 또는 start === end), 해당 위치의 값이 목표 값과 일치하는지 확인하고 일치한다면 그 인덱스를 targets에 추가합니다.

탐색이 끝나면 pick은 Math.random()과 Math.floor()를 조합해 수집된 인덱스들 중 하나를 균등한 확률로 선택하여 반환합니다.

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다. 실행할 때마다 1, 4, 7 중 무작위 값이 출력됩니다.

4