JavaScript - getItemFromTwoSortedArrays

 

문제 설명 : 길이가 m, n이고 오름차순으로 정렬되어있는 2개의 자연수 배열을 입력받은 뒤 전체 배열 요소(2개 배열 전체)에서 k번째 요소를 찾아서 리턴해야합니다. 단 시간복잡도가 중요합니다.

 

입력

인자 1 : arr1

• 자연수를 요소로 갖는 배열
• arr1.length는 m

인자 2 : arr2

• 자연수를 요소로 갖는 배열
• arr2.length는 n

인자 3 : k

• number 타입의 0 이상의 정수

출력

• number 타입을 리턴해야 합니다.

주의사항

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

Advanced

• 단순히 처음부터 끝까지 찾아보는 방법(O(K)) 대신 다른 방법(O(logK))을 탐구해 보세요.
• 이 문제는 알고리즘의 시간복잡도가 가장 중요하다.

힌트

• 이진 탐색(binary search)을 응용하여 해결합니다.
• 이진 탐색 알고리즘의 예시를 보고 응용하세요 

입출력 예시

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번째 요소를 리턴해야겠다고 단순하게만 생각했다.

그러나 시간복잡도에서 테스트 통과가 되지 않았다....

const getItemFromTwoSortedArrays0 = function (arr1, arr2, k) {
    // TODO: 여기에 코드를 작성합니다.
    let arr3 = arr1.concat(arr2)
    arr3.sort(function(a,b){
        return a-b;
    })
    console.log("arr3[k-1]",arr3[k-1])


    return Number(arr3[k-1])
}

 

 

두 번재 레퍼런스 코드

이진 탐색을 응용하고 

 

const getItemFromTwoSortedArrays = function (arr1, arr2, k) {
    let leftIdx = 0,
      rightIdx = 0;
  
    while (k > 0) {
      // 이진 탐색을 위해 각 배열에서 k를 절반으로 쪼개서 카운트 한다.
      //Math.ceil() 함수는 주어진 숫자보다 크거나 같은 숫자 중 가장 작은 숫자를 integer 로 반환합니다.
      let cnt = Math.ceil(k / 2);
      console.log("cnt",cnt)
      let leftStep = cnt,
        rightStep = cnt;

      // 카운트가 남았음에도 배열의 끝에 도달하면 k를 나머지 배열쪽으로 넘긴다.
	  // 배열의 끝까지 갈때 break문 동작 
      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);
  };