Algorithm problem-18

1. 문제

• 배열 2개를 전달받아, 2개 배열의 요소 중 k번째 요소를 리턴

2. 시도

• 각 배열을 카운트 해주고, 전체 카운트도 저장해 준다
• 배열 1과 2의 요소들을 비교해서 작은 쪽을 카운트 올려주고 전체 카운트도 올린다
• 카운트 할 때의 작은 값을 임의 변수에 저장해 둔다
• while문으로 전체 카운트가 k보다 작은 동안 계속 비교해서 카운팅한다
• 카운트가 k - 1일 때 탈출, 저장해 둔 변수를 리턴해준다
• 시간복잡도를 해결하지 못했음

3. 수도코드

const getItemFromTwoSortedArrays = function (arr1, arr2, k) {
  let one = 0, two = 0, cnt = 0, cur = 0;
  while (cnt < k) {
    if (arr1[one] <= arr2[two]) {
      cur = arr1[one]
      one++
    } else {
      cur = arr2[two]
      two++
    }
    cnt++
  }
  return cur;
}

4. 레퍼런스

const getItemFromTwoSortedArrays = function (arr1, arr2, k) {
  let one = 0, two = 0;
  while (k > 0) {
    let cnt = Math.ceil(k / 2);
    let oneStep = cnt, twoStep = cnt;
    if (one === arr1.length) {
      two = two + k;
      break; }
    if (two === arr2.length) {
      one = one + k;
      break; }
    if (cnt > arr1.length - one) oneStep = arr1.length - one;
    if (cnt > arr2.length - two) twoStep = arr2.length - two;
    if (arr1[one + oneStep - 1] < arr2[two + twoStep - 1]) {
      one = one + oneStep;
      k = k - oneStep;
    } else {
      two = two + twoStep;
      k = k - twoStep; } }
  oneMax = arr1[one - 1] || -1;
  twoMax = arr2[two - 1] || -1;
  return Math.max(oneMax, twoMax);
}