프로그래밍/알고리즘

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

공부하는EJ 2022. 6. 17. 18:14
728x90

getItemFromTwoSortedArrays

문제

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

입력

인자 1 : arr1

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

인자 2 : arr2

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

인자 3 : k

  • number 타입의 0 이상의 정수

출력

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

주의사항

  • 두 배열의 길이의 합은 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))을 탐구해 보세요.

힌트

  • 이진 탐색(binary search)을 응용하여 해결합니다.

 

 

💡 내가 풀었던 smart 하지 않은 방법!

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

    let arr1_index = 0;
    let arr2_index = 0;

    for (i = 0; i < k; i++) {
        if (i === k - 1) {
            if (arr1[arr1_index] <= arr2[arr2_index]) {
                return arr1[arr1_index];
            } else {
                return arr2[arr2_index];
            }
        } else {
            if (arr1[arr1_index] <= arr2[arr2_index]) {
                arr1_index++;
            } else {
                arr2_index++;
            }
        }
    }
};

 

이진탐색을 알고 이해하게 되면 시간복잡도를 낮추어 문제를 해결할 수 있다.

 

💡 이진 탐색이란?

이진 탐색이란 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자하는 값 X와 비교한다. X가 중간값보다 작으면 중간 값을 기준으로 좌측의 데이터를 대상으로 , x가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.

 

예시)

 

오름차순으로 정렬된 배열이 있다. { 2, 3, 4, 5, 6, 7, 8, 9,}

이 배열에서 3을 찾아보면 우선 가운데 값 4를 선택한다. 그럼 4는 5보다 작으니 4는 왼쪽에 존재한다는 것을 알 수 있다.

그 다음 {2, 3, 4}를 대상으로 다시 탐색을 진행한다. 가운데 값이 3을 기준으로 오른쪽에 있다는 것을 확인할 수 있다.

그 다음은 {4}를 대상으로 탐색을 진행하는데, 우리가 원하는 값을 찾은 것이다.

 

 

const getItemFromTwoSortedArrays = function (arr1, arr2, k) {
  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) 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 - leftStep;
    } else {
      rightIdx = rightIdx + rightStep;
      k = k - rightStep;
    }
  }

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

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

 

728x90