문제 : getItemFromTwoSortedArrays

배열 두개를 입력받아 전체 요소 중 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

힌트 : 이진 탐색(binary search)를 응용하여 해결

문제의 접근

단순하게 생각하면 두 배열을 합친다음 정렬시켜서 (k-1)인덱스의 값을 찾으면 된다.

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

//or 

const getItemFromTwoSortedArrays = function (arr1, arr2, k) {
  // TODO: 여기에 코드를 작성합니다.
  let stack = [];
  let i = 0;
  let j = 0;
  while(stack.length < k){
    if(arr1[i] < arr2[j]){
      stack.push(arr1[i])
      i++;
    }else{
      stack.push(arr2[j])
      j++;
    }
  }
  return stack[stack.length-1];
};

콘솔의 경우는 정답을 무사히 반환한다 하지만 역시나 npm ERR가 발생한다. Advanced 함께 해결하라는 말이다...

Advanced

O(n) 복잡도 대신 O(log n)의 복잡도로 구현

이미 문제에서 이진 탐색(binary search) 써서 풀라고 말하는 것이나 다름 없다. 그렇다면 저 문제를 어떻게 이진 탐색으로 해결하느냐가 문제다. 각 배열이 이미 오름차순이라는 점에 포커스를 맞출 필요가 있어 보인다.

• 일단 O(log n)의 복잡도는 무조건 절반만 생각하면 된다. 여기서 배열은 합치든 나누든 의미가 없으니 절반으로 나눠버려야 하는 것은k이다.

• while문을 돌려서 확인하는 데이터의 절반을 날려버려야 한다. 절반 절반 절반...혹은 절반 이상을...

const getItemFromTwoSortedArrays = function (arr1, arr2, k) {
  // TODO: 여기에 코드를 작성합니다.
  let stack = [];
  let max = 0;

  while(stack.length < k){
    let index = Math.ceil((k - stack.length)/2)
    if(arr1[index] > arr2[index]){
      if(arr2.length !== 0){
        let len = arr2.length;
        for(let i = 0; i < (index > len ? len : index); i++){
          max = arr2.shift()
          stack.push(max)
        }
      }
      let len = stack.length;
      if(len >= k) break;
      for(let i = 0; i < (index > len ? len : index); i++){
        if(arr1[i] < max){
          stack.push(arr1.shift())
        }
      }
    }else{
      if(arr1.length !== 0){
        let len = arr1.length;
        for(let i = 0; i < (index > len ? len : index); i++){
          max = arr1.shift()
          stack.push(max)
        }
      }
      let len = stack.length;
      if(len >= k) break;
      for(let i = 0; i < (index > len ? len : index); i++){
        if(arr2[i] < max){
          stack.push(arr2.shift())
        }
      }
    }
  }
  return max
};

콘솔은 매우 잘 돌아간다. 근데 실행시간이 초과된다... 왜지... 코드를 한번 동작하면 분명 연산은 절반 이상으로 돌아간다고 생각한다. 근데 왜 안되는지 전혀 이해가 안간다.

문제를 통해 생각해 볼 것

짜증나서 그냥 레퍼런스를 봤다... 근데 참 어이가 없다. 접근은 비슷한 것 같은데 아마 배열을 사용하고 거기에 접근하는 방식이 for문 이라서 복잡도가 증가한 것 같다.

const getItemFromTwoSortedArrays = function (arr1, arr2, k) {
  // TODO: 여기에 코드를 작성합니다.
  let leftIdx = 0,
    rightIdx = 0;

  while (k > 0) {
    let cnt = Math.ceil(k / 2);
    let leftStep = cnt,
      rightStep = cnt;

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

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

    if (cnt > arr1.length - leftIdx) leftIdxStep = 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 - leftStep;
    } else {
      rightIdx = rightIdx + rightStep;
      k = k - rightStep;
    }
  }

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

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