길이가 m, n이고 오름차순으로 정렬되어 있는 자연수 배열들을 입력받아 전체 요소 중 k번째 요소를 리턴해야 합니다.
자연수를 요소로 갖는 배열
arr1.length는 m
자연수를 요소로 갖는 배열
arr2.length는 n
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
단순히 처음부터 끝까지 찾아보는 방법(O(K)) 대신 다른 방법(O(logK))을 탐구해 보세요.
이진 탐색(binary search)을 응용하여 해결합니다.
const getItemFromTwoSortedArrays = function (arr1, arr2, k) { let gatheredArray = arr1.concat(arr2); let sortedArray = gatheredArray.sort((a, b) => a - b); // return sortedArray[k-1]; }
개발자도구에서 돌렸을 때는 문제가 없었지만 코플릿에서는 에러가 났다
두 배열의 길이의 합이 1,000,000이하라고 했으니 concat하고 sort하는 것에서 시간이 많이 걸리고있는 듯 하다
내가 알아야하는 값은 k번째 요소만 알면 되는데 그걸 위해 concat까지 하고 sort까지 하는건 시간 낭비일 수 있긴 하다..
const getItemFromTwoSortedArrays = function (arr1, arr2, k) {
let count = 0
left = 0 // arr1의 0번째부터 시작
right = 0 // arr2의 0번째부터 시작
let target;
while (count < k) {
if(arr[left] < arr[right]) {
target = arr[left];
left++;
} else { // arr[left] > arr[right]일 경우
target = arr[right];
right++
}
count++ // if문을 돌아도, else문을 돌아도 count는 모두 한번씩 올라간다
}
return target;
}
시간복잡도로 해결한 문제는 레퍼런스를 봐도 모르겠다
à voir ...
const getItemFromTwoSortedArrays = function (arr1, arr2, k) {
let leftIdx = 0,
rightIdx = 0;
while (k > 0) {
// 이진 탐색을 위해 각 배열에서 k를 절반으로 쪼개서 카운트 한다.
let cnt = Math.ceil(k / 2);
let leftStep = cnt,
rightStep = cnt;
// 엣지 케이스
// 카운트가 남았음에도 배열의 끝에 도달하면 k를 나머지 배열쪽으로 넘긴다.
if (leftIdx === arr1.length) {
rightIdx = rightIdx + k;
break;
}
if (rightIdx === arr2.length) {
leftIdx = leftIdx + k;
break;
}
// 엣지 케이스
// 현재 카운트가 남아있는 후보 요소들보다 많을 경우, leftStep(현재 할당량)을 남아있는 요소들의 개수로 바꾼다.
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 = k - leftStep;
} else {
rightIdx = rightIdx + rightStep;
k = k - rightStep;
}
}
leftMax = arr1[leftIdx - 1] || -1;
rightMax = arr2[rightIdx - 1] || -1;
return Math.max(leftMax, rightMax);
};