[Algorithm] 두 배열에서 k 번째 수 찾기 Javascript(getItemFromTwoSortedArrays 알고리즘)

문제

길이가 m, n이고 오름차순으로 정렬되어 있는 두개의 배열이 주어진다. 각 배열은 자연수로 이루어져 있고, 두 배열을 합친 전체 배열에서 k 번째 요소를 출력한다.

 

입력

• 자연수를 요소로 가지는 배열 arr1
• arr1.length는 m
• 자연수를 요소로 가지는 배열 arr2
• arr2.length는 n
• k
• number 타입의 0 이상 정수

출력

• nubmer 타입

주의사항

• 두 배열의 합은 1,000,000 이하

입출력 예시

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

 

 

 

 

풀이

Solution 1

굉장히 간단한 생각으로 답을 도출할 수 있다. arr1, arr2 두개의 배열을 하나로 합친 다음 k번째 요소를 출력해주면 된다.

const getItemFromTwoSortedArrays = function (arr1, arr2, k) {

    let arr3 = [...arr1, ....arr2]
    arr3 = arr3.sort((a,b)=>a-b)

    return arr3[k];
}

Solution 2

두개의 배열은 반복문으로 순회하면서 각 요소들을 비교해주는 작업이 필요하다. 만약 arr1[현재요소]가 arr2[현재요소]보다 작은 경우 출력값은 arr1[현재요소]가 되는 식으로 반복횟수가 주어진 k 와 같아질 때 까지 반복한다.

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


    let firstCnt = 0, secondCnt=0;
    let target= 0;

    while(k > (firstCnt+secondCnt)){
      if(arr1[firstCnt] < arr2[secondCnt]){
        target = arr1[firstCnt];
        firstCnt++;
      }else{
        target = arr2[secondCnt];
        secondCnt++;
      }
    }
    return target;


  };

 

Solution 3

위 두가지 방법 모두 시간복잡도는 O(N)가 나오게 된다. 즉 찾고자 하는 요소가 크면 클 수록 시간 복잡도는 비례해서 상승하게 된다. 문제의 주의사항에 각 배열의 총합 길이가 100만 이하라고 했으니 만약, k=998,112 인 경우를 생각하면 연산횟수가 너무 많아진다.

이런 문제를 해결하기 위해서 이진 탐색을 통해 시간복잡도를 O(Log N)으로 낮추는 방법이 있다. 아래 코드 보고 로직이 어떻게 구성되는지 이해할 수 있다면 알고리즘 구현에 자신감을 가져도 좋다. 1시간째 보고 있는데, 코드 이해가 안되서 미래의 나에게 토스하고 왔다. 

 

const getItemFromTwoSortedArraysAdvanced = function (arr1, arr2, k) {
    let leftIdx = 0,
      rightIdx = 0;
  
    while (k > 0) {
      
      let cnt = Math.ceil(k / 2);
      let leftStep = cnt, // 현재 할당량
        rightStep = cnt;  // 현재 할당량

        console.log(`
        leftIdx = ${leftIdx},
        leftStep = ${leftStep}
        rightIdx = ${rightIdx};
        rightStep =${rightStep}
        k = ${k}
        cnt = ${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;
      }
    }
    console.log(`
        leftIdxFinal = ${leftIdx},
        rightIdxFinal = ${rightIdx};
      `)
  
    leftMax = arr1[leftIdx - 1] || -1;
    rightMax = arr2[rightIdx - 1] || -1;
  
    return Math.max(leftMax, rightMax);
  };

 

 

 

 

[Algorithm] Balance Brackets in JS ( 스택(stack) 알고리즘 활용 )

 

[Algorithm] powerSet 알고리즘,문자열 부분 집합 문제 Javascript, Node.js