[Binary Search 이진탐색] getItemFromTwoSortedArrays

문제 - getItemFromTwoSortedArrays

길이가 m, n이고 오름차순으로 정렬되어 있는 자연수 배열들을 입력받아 전체 요소 중 k번째 요소를 리턴해야 합니다.

입력

• 인자 1 : arr1
  자연수를 요소로 갖는 배열
  arr1.length는 m
• 인자 2 : arr2
  자연수를 요소로 갖는 배열
  arr2.length는 n
• 인자 3 : k
  number 타입의 0 이상의 정수

주의사항

두 배열의 길이의 합은 1,000,000 이하입니다.
어떤 배열 arr의 k번째 요소는 arr[k-1]을 의미합니다.

입출력 예시

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

Advanced

단순히 처음부터 끝까지 찾아보는 방법(O(K)) 대신 다른 방법(O(logK))을 탐구해 보세요.

풀이

풀이 1. 시간복잡도 고려 없이

const getItemFromTwoSortedArrays = function (arr1, arr2, k) {
  return [...arr1, ...arr2].sort((a, b) => a-b)[k-1];
};

풀이 2. 시간복잡도 O(K)

두 배열의 각각 첫 번째 요소부터 둘 중 작은 수를 비교해서 K 번째까지 구하는 방법이다.
1. arr1[0], arr2[0]를 비교해서 작은 수는 두 배열을 합쳤을 때 가장 첫 번째 수가 될 것이다.

• 만약 arr1[0] < arr2[0] 라면,
  합쳐진_새로운_배열 = [ arr1[0], ... , K번째 요소 ] 일 것이다.

2. 앞의 작은 숫자는 새로운 배열에 넣었으므로 건너뛰고, 그 다음 숫자와 비교해서 더 작은 숫자가 합쳐진 새로운 배열의 두 번째 숫자가 도리 될 것이다.

• 만약 arr1[1] < arr2[0] 라면,
  합쳐진_새로운_배열 = [ arr1[0], arr1[1]... , K번째 요소 ] 가 된다.

3. 이런 식으로 계속 비교해서 K 번째 숫자까지 구한다.
   단, 문제에서 K번째 숫자의 인덱스는 [K - 1] 임을 기억하자!

const getItemFromTwoSortedArrays = function (arr1, arr2, k) {
  let left = 0, right = 0;
  let answer;
  
  for(let i = 0; i < k; i++){
    if(arr1[left] < arr2[right]){
      answer = arr1[left];
      left++;
    }else{
      answer = arr2[right];
      right++;
    };

  }

  return answer
};

풀이3. [Advanced] 시간복잡도 O(logK)

K번째 숫자를 구할 때, 그 앞 [1번째, 2번째, ..., K-1번째] 까지의 숫자들은 K보다 작기만 하면 되고, 순서는 상관이 없다.

1. 엣지케이스를 제외하고 K번째 숫자는 arr1에서 절반, arr2에서 절반이 나올 수 있다.

2. arr1과, arr2에서 각각 (K ÷ 2) 번째의 숫자를 찾아 비교해본다.

• 만약 arr1[k÷2] < arr2[K÷2] 라면,
  arr1[0] < arr1[1] < ... < arr1[k÷2] 이므로,
  [ arr1[0], arr1[1], ... , arr1[k÷ 2], (K ÷ 2) + 1 번째 숫자, ..., K번째 숫자 ] 가 된다.
  

3. 이제 남은 나머지 (K ÷ 2) 개의 숫자들을 반복해서 찾으면 된다.

4. 먼저 K는 다시 절반으로 쪼개주고,

• 마지막 숫자 1개를 구하는 경우를 위해 소수점은 올림해준다.

5. 풀이 2.에서와 마찬가지로, 더 작은 수의 다음 수와 다시 비교해본다.

6. 반복해서 K 번째 숫자를 찾으면 끝

엣지케이스 처리

[edge case1] 현재 카운트(K)가 남아있는 후보 요소들보다 많을 경우, 현재 할당량(K)을 남아있는 요소들의 개수로 바꾼다.

• 예를 들어,
  arr1 = [1, 2, 3, 4, 5], arr2 = [1, 2, 3] 일 때,
  8번째 요소를 찾는다면,
  • 그 절반인 4번째 요소가 arr1에는 있지만, arr2에는 없으므로,
  • arr2는 3번째 요소로 비교한다.

[edge case2] 카운트가 남았음에도 배열의 끝에 도달하면 k를 나머지 배열쪽으로 넘긴다.

• 예를 들어,
  arr1 = [1, 2, 3, 4, 5, 6], arr2 = [1]일 때
  6번째 요소를 찾는다면,
  • K ÷ 2 = 3 이고, arr1[2] > arr2[0] 이된다.
  • 그 다음,
    arr2[0]으로 1칸을 채웠으니, K = 5 칸의 숫자들을 더 찾아야 한다.
  • K ÷ 2 = 3 (소수점 올림)일 때, arr2에는 더이상 비교할 요소가 없으므로,
  • arr1에 남은 K = 5 칸 전부를 넘긴다.
    즉, arr1의 5번째 숫자 5가 답이된다.

const getItemFromTwoSortedArrays = function (arr1, arr2, k) {
  let leftIdx = 0,
    rightIdx = 0;

  while (k > 0) {
    // 이진 탐색을 위해 각 배열에서 k를 절반으로 쪼개서 카운트 한다.
    let cnt = Math.ceil(k / 2);
    let leftStep = cnt,
      rightStep = cnt;

    // 엣지 케이스
    // 카운트가 남았음에도 배열의 끝에 도달하면 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);
};