음.. 정렬되고, 순회되어 변경된 array에서 해당 key를 찾고 index를 반환하는 알고리즘이다. 당장 생각나는 바로는 무식하게 for문으로 돌려서 O(n)으로 찾을 수 있겠지만, 문제에서 찾고자 하는 바는 O(logn)의 시간복잡도를 원한다.
음.. 이진트리를 쓰면 O(logn)으로 줄여볼 수 있을거 같은데, 이진트리를 쓰지않고서 할 수 있는 방법이 있을까?
practice.geeksforgeeks.org/problems/search-in-a-rotated-array/0
Search in a Rotated Array | Practice | GeeksforGeeks
practice.geeksforgeeks.org
문제
Given a sorted and rotated array A of N distinct elements which is rotated at some point, and given an element K. The task is to find the index of the given element K in the array A.
Input:
The first line of the input contains an integer T, denoting the total number of test cases. Then T test cases follow. Each test case consists of three lines. First line of each test case contains an integer N denoting the size of the given array. Second line of each test case contains N space separated integers denoting the elements of the array A. Third line of each test case contains an integer K denoting the element to be searched in the array.
Output:
Corresponding to each test case, output the index of the element found in the array. If element is not present, then output -1.
Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 107
0 ≤ Ai ≤ 108
1 ≤ K ≤ 108
Example:
Input:
3
9
5 6 7 8 9 10 1 2 3
10
3
3 1 2
1
4
3 5 1 2
6
Output:
5
1
-1
Explanation:
Testcase 1: 10 is found at index 5.
우선 무식하게 for문을 돌려보았다.
코드
package rotate;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.stream.Collectors;
public class SearchInRotatedArray {
public static int searchPivot(Integer[] arr, int n, int k) {
for(int i=0; i<n; i++) {
if(arr[i] == k) return i;
}
return -1;
}
public static void main(String[] args) {
try(BufferedReader bufferedReader = new BufferedReader(
new InputStreamReader(System.in))
)
{
int testCase = Integer.parseInt(bufferedReader.readLine());
StringBuilder stringBuilder = new StringBuilder();
for(int i=0; i<testCase; i++) {
int n = Integer.parseInt(bufferedReader.readLine());
Integer[] arr = new Integer[n];
Arrays.stream(bufferedReader.readLine().split(" "))
.map(s->Integer.parseInt(s))
.collect(Collectors.toList())
.toArray(arr);
int k = Integer.parseInt(bufferedReader.readLine());
stringBuilder.append(
searchPivot(arr, n, k) + "\n");
}
System.out.println(stringBuilder.toString());
}catch(IOException ex) {
ex.printStackTrace();
} catch(NumberFormatException ex) {
ex.printStackTrace();
}
}
}
최대한 I/O에 쓰이는 입출력 시간을 줄이는 꼼수를 써서 드는 전체 time을 줄여보았다.
내 적당적당함에 절망해버렸다. 이 챕터에서는 아직 다른 자료구조를 배우지 않은 상태이고, 방법이 있을것이리라 생각하고 좀 더 고집을 부려보기로 했다.
public static int searchPivot(Integer[] arr, int n, int k) {
for(int i=0; i<n; i++) {
if(arr[0]>k && n>1 && arr[1]>arr[0]) {
for(int j=n-1; j>0; j--) {
if(arr[j]==k) return j;
}
return -1;
}
if(arr[i] == k) return i;
}
return -1;
}조건을 주었다.
- 배열의 첫 번째 요소가 찾으려는 피벗보다 크고
- 배열의 사이즈가 1보다 크고, 배열의 두 번째 요소가 첫 번째 요소보다 클 때(즉, 정렬되어있을 때)
배열을 뒤에서부터 순회하면 되겠네!
문제에서는 어떻게 풀었는지 확인해 보았다. binary search를 활용했잖어..?
예제로 나온 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.stream.Collectors;
public class SearchInRotatedArray {
public static int pivotedBinarySearch(Integer arr[], int n, int key)
{
int pivot = findPivot(arr, 0, n - 1);
// If we didn't find a pivot, then
// array is not rotated at all
if (pivot == -1)
return binarySearch(arr, 0, n - 1, key);
// If we found a pivot, then first
// compare with pivot and then
// search in two subarrays around pivot
if (arr[pivot] == key)
return pivot;
if (arr[0] <= key)
return binarySearch(arr, 0, pivot - 1, key);
return binarySearch(arr, pivot + 1, n - 1, key);
}
/* Function to get pivot. For array
3, 4, 5, 6, 1, 2 it returns
3 (index of 6) */
public static int findPivot(Integer arr[], int low, int high)
{
// base cases
if (high < low)
return -1;
if (high == low)
return low;
/* low + (high - low)/2; */
int mid = (low + high) / 2;
if (mid < high && arr[mid] > arr[mid + 1])
return mid;
if (mid > low && arr[mid] < arr[mid - 1])
return (mid - 1);
if (arr[low] >= arr[mid])
return findPivot(arr, low, mid - 1);
return findPivot(arr, mid + 1, high);
}
/* Standard Binary Search function */
public static int binarySearch(Integer arr[], int low, int high, int key)
{
if (high < low)
return -1;
/* low + (high - low)/2; */
int mid = (low + high) / 2;
if (key == arr[mid])
return mid;
if (key > arr[mid])
return binarySearch(arr, (mid + 1), high, key);
return binarySearch(arr, low, (mid - 1), key);
}
public static void main(String[] args) {
try(BufferedReader bufferedReader = new BufferedReader(
new InputStreamReader(System.in))
)
{
int testCase = Integer.parseInt(bufferedReader.readLine());
StringBuilder stringBuilder = new StringBuilder();
for(int i=0; i<testCase; i++) {
int n = Integer.parseInt(bufferedReader.readLine());
Integer[] arr = new Integer[n];
Arrays.stream(bufferedReader.readLine().split(" "))
.map(s->Integer.parseInt(s))
.collect(Collectors.toList())
.toArray(arr);
int k = Integer.parseInt(bufferedReader.readLine());
stringBuilder.append(
pivotedBinarySearch(arr, n, k) + "\n");
}
System.out.println(stringBuilder.toString());
}catch(IOException ex) {
ex.printStackTrace();
} catch(NumberFormatException ex) {
ex.printStackTrace();
}
}
}
.
으음.. index를 divided 한 것까지는 생각했는데, 머리가 안돌아가는지 디버깅만 계속하다가 실패했다. 하지만, 예제로 나온 코드를 보니 내가 정답에 거의 근접했다는 것을 볼 수 있었다 ㅠ.. 좀만 더 시간 투자해볼껄..
결과
😒 input data 적용은 저번 코드를 그대로 참고했다.
🤔 sorted, rotated를 활용한 것까지는 좋은데..
🤢 sorted면, 바로 이진트리 생각난 것도 좋은데, 왜 그 내부 로직은 적용할 생각을 못한걸까
😜 생각도 좀 하자 바보야..
* 위에서 제시한 코드 이외에도 여러 방법이 나와있고, 각각 친절하게 원리와 시간복잡도 및 공간복잡도가 명시되어있으니 필요하면 직접 사이트에서 봐보는것을 추천한다.
www.geeksforgeeks.org/array-rotation/
Program for array rotation - GeeksforGeeks
A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
www.geeksforgeeks.org