CodingBat Java: Array-3 (linearIn)

Given two arrays of ints sorted in increasing order, outer and inner, return true if all of the numbers in inner appear in outer. The best solution makes only a single "linear" pass of both arrays, taking advantage of the fact that both arrays are already in sorted order.

linearIn([1, 2, 4, 6], [2, 4]) → true
linearIn([1, 2, 4, 6], [2, 3, 4]) → false
linearIn([1, 2, 4, 4, 6], [2, 4]) → true

---

Solution

이번 문제는 outer 배열에 Inner 배열의 원소가 모두 포함되면 true를 반환하고, 모두 포함하지 않으면 false를 반환하는 문제이다. 여기에서 주어지는 두 배열은 모두 오름차순으로 정렬된 배열이므로, 이 사실을 가지고 문제를 풀이하였다.

 

1. 먼저 lnner 배열의 첫 번째 원소가 outer 배열의 어디에 위치하는지 검색하여 위치한 인덱스를 반환한다. 여기에서는 탐색 알고리즘 중, 정렬된 배열에 대해 탐색하는데 가장 적합한 BinarySearch 알고리즘을 사용한다.

2. outer 배열로부터 찾은 인덱스의 다음 인덱스와 Inner 배열의 두 번째 원소와의 비교를 시작한다. 이렇게 outer 배열의 원소와 lnner 배열의 원소 비교는 오름차순이므로, LinearSearch로 앞에서 비교를 진행한다.

3. 탐색 및 비교를 통해 Inner 배열의 모든 원소가 outer 배열에 존재할 경우 true를 반환하고, outer 배열에 존재하지 않는 Inner 배열의 원소가 있을 경우 false를 반환한다.

 

---

Code

 

---

 

Algorithm

Arrays.binarySearch() 함수에 대한 자바 공식문서의 정의는 다음과 같다.

 

이 함수에서 사용한 탐색 알고리즘은 이진 탐색 알고리즘으로, 이를 사용하기 위해서는 정렬된 배열이라는 조건이 필요하다. 

그러므로 여기에서 사용한 이진 탐색(Binary Search) 알고리즘의 과정을 알아보자.

 

이진 탐색 알고리즘의 진행방법은 다음과 같다.

1. 먼저 찾고자 하는 값을 find, 탐색할 배열의 중간 인덱스를 index로 정한다.

2. 정렬된 배열에 대해서 중간 인덱스의 원소값과 찾고자 하는 값을 비교하여 기준값보다 크면 오른쪽 배열을, 작으면 왼쪽 배열을 탐색한다.

3. index의 원소값보다 find가 큰 경우 배열의 index+1 인덱스 부터 끝까지인 오른쪽 배열이 기준이 되고, index의 원소값보다 find가 작은 경우 처음부터 index 인덱스까지가 배열이 기준이 된다. 기준이 되는 배열의 크기가 1이 되거나, 원소를 찾는 경우가 아니면 1~2번 과정을 반복한다.

4. find 값을 찾은 경우 이 값의 인덱스를 반환하고, 찾지 못한 경우 -1을 반환한다.

 

위 그림은 정렬된 배열에 대한 BinarySearch 알고리즘과 LinearSearch 알고리즘의 대한 임의의 결과이다. BinarySearch가 LinearSearch보다 빠르다는 것을 알 수 있다.

 

모든 경우의 수가 이러한 결과를 나타내지는 않지만, 이러한 여러 반복을 통한 결과로 linearSearch의 시간복잡도는 O(n), BinarySearch의 시간복잡도는 O(logn)으로 BinarySearch가 훨씬 빠르다는 것을 알 수 있었다.

---

 

 

출처: https://blog.steamedu123.com/entry/티스토리-서식-글-쓰기 [모두의 블로그]  

https://devlog-wjdrbs96.tistory.com/106