[알고리즘] getItemFromTwoSortedArrays

길이가 m, n이고 오름차순으로 정렬되어 있는 자연수 배열들을 입력받아 전체 요소 중 k번째 요소를 리턴해야 한다. (실제로 리턴하는 값은 인덱스가 k-1인값이라고 생각하면 됨. 인덱스는 0부터 시작하니까.)

arr1, arr2, k가 주어진다.

문제만 봐서는 잘 이해가 안 돼서 입출력 예시를 살펴봐야했다.

let arr1 = [1, 4, 8, 10];
let arr2 = [2, 3, 5, 9];
let result = getItemFromTwoSortedArrays(arr1, arr2, 6);
console.log(result); // --> 8

arr1 = [1, 1, 2, 10];
arr2 = [3, 3];
result = getItemFromTwoSortedArrays(arr1, arr2, 4);
console.log(result); // --> 3

두 배열의 모든 요소들 중에서 k번째(인덱스 k-1) 요소를 찾는 거라고 보면 되는데, 처음에 접근할 때 arr1, arr2를 모두 합쳐서 & 오름차순 정렬해서 구해보려고 했는데 그런 접근으로 푸는 문제가 아니라고 한다...

힌트로 이진 탐색을 응용해서 풀어야 한다고 되어 있는데... 쉽지 않았다...

// naive solution
 const getItemFromTwoSortedArrays = function (arr1, arr2, k) {
	   let cnt = 0,
	     left = 0,
	     right = 0;
	   let target;
	   while (cnt < k) {
         //k보다 cnt가 작을 때까지만 반복문이 돌아감 
	     if (arr1[left] < arr2[right]) {
           //각 arr의 맨 처음 인덱스부터 크기를 비교한다 
           //만약 arr1의 인덱스 0 값이 arr2의 인덱스 0값보다 작으면
           //target은 arr1의 0번째 인덱스이고, left는 1이 증가함 
           //이런식으로 left나 right를 증가시켜서 각 arr1,2의 요소들의 값을 
           //순서대로 target에 바꿔 할당하고 
           //다음 반복문으로 넘어가기 전 cnt를 1씩 증가시켜 횟수를 센다 
           //(아마 cnt가 카운트를 뜻하는 게 아닌가 싶다)
           //그래서 cnt가 k보다 작을 때 (우리는 k-1 인덱스를 구해야 하니까)
           //반복문이 종료되고, target에 담긴 값을 반환한다 
	       target = arr1[left];
	       left++;
	    } else {
	      target = arr2[right];
	right++;
	     }
	     cnt++;
	}
	return target;
};

그냥 하나 하나 arr1과 arr2의 요소를 비교해가며 target을 찾는 방법은 위와 같다. 그러나 이 경우에는 0(k)라서 이진 탐색을 이용해야만 O(logK)로 문제를 해결할 수 있다.

이진탐색을 이용하면 아래와 같다.

참고로 엣지 케이스란 알고리즘이 처리하는 데이터의 값이 알고리즘의 특성에 따른 일정한 범위를 넘을 경우에 발생하는 문제를 가리킨다고 한다.

아래 해결법의 포인트도 이진 탐색처럼 구할 값을 반으로 나눈다는 점인 것 같다. arr1과 arr2가 모두 오름차순으로 정렬이 되어 있기 때문에 가능한듯.

O(logK) 솔루션이 완전히 이해가 된 건 아니라 조금 더 살펴보고 추가할 내용이 있으면 추가해야겠다.

// O(logK) solution
const getItemFromTwoSortedArrays = function (arr1, arr2, k) {
  //아래에 만들어진 left, rightIdx는 포인터 변수 (현재 위치)
  let leftIdx = 0,
    rightIdx = 0;

  while (k > 0) {
    //K가 0보다 클 동안만 반복한다 
    
    // 이진 탐색을 위해 각 배열에서 k를 절반으로 쪼개서 카운트 한다.
    let cnt = Math.ceil(k / 2);
    //카운트 하기 위한 변수 
    let leftStep = cnt,
      rightStep = cnt;

    // 엣지 케이스
    // 카운트가 남았음에도 배열의 끝에 도달하면 k를 나머지 배열쪽으로 넘긴다.
    //다음 반복문으로 넘아가기 직전 k값에서 left/rightStep 값을 빼주고도 k값이 남으면 넘기는듯 
    if (leftIdx === arr1.length) {
      rightIdx = rightIdx + k;
      break;
    }

    if (rightIdx === arr2.length) {
      leftIdx = leftIdx + k;
      break;
    }

    // 엣지 케이스
    // 현재 카운트가 남아있는 후보 요소들보다 많을 경우, leftStep(현재 할당량)을 남아있는 요소들의 개수로 바꾼다.
    if (cnt > arr1.length - leftIdx) leftStep = arr1.length - leftIdx;
    if (cnt > arr2.length - rightIdx) rightStep = arr2.length - rightIdx;

    // 두 배열의 현재 검사 요소 위치를 비교해서, 그 값이 작은 배열은 비교한 위치 앞에 있는 요소들을 모두 후보군에서 제외시킨다.
    if (arr1[leftIdx + leftStep - 1] < arr2[rightIdx + rightStep - 1]) {
      leftIdx = leftIdx + leftStep;
      // 처리가 끝나면 k값을 절반으로 떨어뜨린다.
      k = k - leftStep;
    } else {
      rightIdx = rightIdx + rightStep;
      k = k - rightStep;
    }
  }

  leftMax = arr1[leftIdx - 1] || -1;
  rightMax = arr2[rightIdx - 1] || -1;

  return Math.max(leftMax, rightMax);
};