Toy 문제 18

문제

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

 

Advanced

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

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

 

수도코드(해석)

두 배열을 합쳐서(concat) sort하고 해당 k위치에 해당되는 값을 뽑으면 되지않을까 라는 생각에 좀 혼란에 빠졌는데

sort의 시간복잡도 O(log N) 이고 K위치를 바로 출력하는건 O(1) 이니까 시간복잡도가 충분한 줄 알았지만, 배열을 합치는것이 O(N)이기 때문에 어드벤스를 충족시킬수없는 것을 알았습니다.

그렇기 때문에 문제를 해결할 때에 arr1, arr2를 합치지 않는 것을 볼 수 있습니다.

(처음에는 뭐 그렇게 복잡하게 해야하나 싶어서 이해가 안갔다)

 

그래서 배열은 그대로 두고 k라는 변수에 들어오는 숫자로만 문제를 해결을 해야합니다.

 

k라는 변수를 반으로 나눠서 각자 부여하고

배열의 길이가 k 크기보다 작을 수 있는 부분에 대한 코드와

각 배열의 요소가 고루 배열되어있지않고 작은 값이 어느 한 배열에 쏠려 있을 수 있기 때문에 거기에 대한 코드를 작성 해 줍니다.

 

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);
};