[자료구조/알고리즘] 211101 getItemFromTwoSortedArrays #이진탐색응용 #while문

📌 두개의 정렬된 배열에서 item 뽑아내기

문제
길이가 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]을 의미합니다.

문제를 제대로 읽고 코드를 짜야겠다. 오름차순 정렬되어있다는 걸 제대로 확인했어야 했다. advanced로 시간복잡도를 해결하려면 코드가 더 많이 복잡해진다.

☑ 처음 접근방법

두개의 배열을 꼭 합쳐야 한다고 생각했었다. 그리고 앞서 풀었던 이진탐색을 응용하라고 힌트에 써져있어서 왼쪽 인덱스 가운데 인덱스 그리고 오른쪽 인덱스를 할당하고 시작했다. 물론 이렇게 쓰면서 이건 아닌 거 같은데 느끼긴 했다ㅠ

// 두개의 배열을 합치고, 정렬한다
  let newArr = arr1.concat(arr2)
  let sortArr = newArr.sort((a,b) => a-b)
  // 왼쪽,오른쪽 인덱스의 반을 나눈다. 
  let left = 0
  let right = sortArr.length - 1
  while(left <= right) {
    const mid = parseInt((left + right)/2)
    for(let k=0; i < sortArr.length; i++) {
        if(sortArr[k-1] === sortArr[mid]) {
          return sortArr[k-1]
        } 
        else { 
           if(sortArr[k-1] < sortArr[mid]) { right = mid -1 }
           else { left = mid + 1}
        }  
      }
    }
};

☑ naive solution

시간복잡도를 해결하지 못하고 순차적으로 조회하는 접근방법이다.

• count , left , right의 변수를 설정하고 초기값을 0을 할당한다. 그리고 target선언. target은 해당하는 인덱스의 값(인덱스가 아님)
• count 가 k보다 클때 계속 반복하기 때문에 while문 작성
• 그 while문 안에서 만약 arr[left]보다 arr[right]가 크다면 그리고 크지 않다면 으로 나눈다. (초기값이 0이니 arr1/arr2 의 0번째 인덱스끼리 비교하게 된다.)
• arr1[right]의 값이 arr2[right]보다 크다면 target = arr1[left] 할당. 그리고 right++ 해준다
• arr1[right]의 값이 arr2[left]보다 크다면 target = arr[left]
  그리고 left++ 해준다

하위 두개 부분은 코드를 보면서 설명하는게 좋을 것 같다.

const getItemFromTwoSortedArrays = function (arr1, arr2, k) {
  let count = 0,
  left = 0,
  right = 0;
  let target;
   while (count < k) {
     if (arr1[left] < arr2[right]) {
       target = arr1[left]; // 해당값을 찾기위해 계속 진행되고 count도 그에 따라 증가한다. while문을 벗어나는 순간 인덱스의 값이 나온다
       left++;
     } else {
       target = arr2[right]; // 해당값을 찾기위해 계속 진행되고 count도 그에 따라 증가한다. while문을 벗어나는 순간 인덱스의 값이 나온다
       right++;
     }
     count++;
   }
   return target;
 };