Intersection of Two Arrays II 자바스크립트

이번 알고리즘 스터디 때 이진탐색을 주제로 한 문제로 선정했다.

다만 풀면서 이렇게 푸는것 보다 해시로 푸는게 더 나았을 거라는 생각을 떨칠 수 없었다고...

그래도 이진탐색에 익숙해지려고 이진탐색을 적용해 풀었다.

 

const intersect = function (nums1, nums2) {
	const answer = [];
	let sortedArray = nums1;
	let justArray = nums2;
	if (nums1.length > nums2.length) {
		sortedArray;
		justArray;
	} else {
		sortedArray = nums2;
		justArray = nums1;
	}
	sortedArray.sort((a, b) => a - b);

	for (let i = 0; i < justArray.length; i++) {
		let startIndex = 0;
		let endIndex = sortedArray.length - 1;
		while (startIndex <= endIndex) {
			let middleIndex = Math.floor((startIndex + endIndex) / 2);
			let target = sortedArray[middleIndex];
			let value = justArray[i];
			if (target === value) {
				answer.push(target);
				sortedArray.splice(middleIndex, 1);
				break;
			} else {
				if (value < target) {
					endIndex = middleIndex - 1;
				} else {
					startIndex = middleIndex + 1;
				}
			}
		}
	}
	console.log(answer);
	return answer;
};

문제풀이 중 릿코드에는 follow up이라고 따로 표시된 지침이 있길래 최대한 따르면서 풀려고 노력했다.

• 두 배열의 길이가 길 때도 짧을 때도 있는데 어떤 경우가 더 좋은 알고리즘인가?
  • 두 배열 중 짧은 길이의 배열을 for문을 순회하는 역할로 사용하도록 코드를 짰다.
  • 1개의 요소만 찾는 평범한? 이진탐색이었다면 그냥 while문 안에서 끝났지만, 여러개의 요소를 비교하기 때문에 for문을 피할 수 없었다. 그나마 조금 더 빠른 방법은 for문의 길이를 줄이는 것이라고 판단했다..
• 이진 탐색을 진행하면서 중복되는 결과값을 제거하기위해 기준이 되는 배열(긴 배열)에서 타겟이 된 값을 찾고나면 splice로 해당 요소를 제거해줌.
  • 배열에서 요소를 제거하는 방법은 1. splice 2. delete 가 있는데, 전자는 요소와 값 모두 삭제되고 후자는 값만 삭제되기 때문에 undefined로 남는다.
  • 이는 loop를 돌 때 undefined까지 돌기 때문에 요소를 삭제해주는 slice를 사용하는게 좋다고 생각했다.
• 위 코드의 시간복잡도는 nlogn이다. 이진탐색을 시행하지면 그 횟수는 for문의 배열 길이 만큼이기 때문이다.

---

그 전에 파이썬으로 문제를 풀 때는 문법이 간편해서 좋다고 생각했다.

자바스크립트를 더 잘 알고싶어서 자바스크립트로 문제를 풀고있는데, 처음엔 너무 어렵고 계속 파이썬으로 넘어갈까 많은 고민을 했다.

(특히 백준문제 풀 때 readline 설정 할 때 마다 너무 ... 생략)

그래서 프로그래머스랑 릿코드로 넘어왔는데 넘어오면서 슬슬 자스에도 익숙해지고

글로만 읽었던 프로토타입에 대해서도 더 자세히 알게되고..

일석이조의 효과를 보고있는 것 같기는 하다.

 

화이퉹~~!