[Practice Algorithm, GeeksForGeeks] Given a sorted and rotated array, find if there is a pair with a given sum

---

정렬되고, 순회되어 변경된 배열에서 주어진 sum의 값에 더해지어 만족되는 value pair 쌍을 구하는 문제이다. 본래는 while문으로 O(n!)간단하게 만들어 볼 수 있으나, binary search로 max값에 해당하는 Pivot을 찾아내고, 경우에 따라 다른 시간복잡도를 보이는 알고리즘을 짜보았다.. ㅠ

 

www.geeksforgeeks.org/given-a-sorted-and-rotated-array-find-if-there-is-a-pair-with-a-given-sum/

Given a sorted and rotated array, find if there is a pair with a given sum - GeeksforGeeks

---

문제

Input: arr[] = {11, 15, 6, 8, 9, 10}, x = 16

Output: true There is a pair (6, 10) with sum 16

Input: arr[] = {11, 15, 26, 38, 9, 10}, x = 35

Output: true There is a pair (26, 9) with sum 35

Input: arr[] = {11, 15, 26, 38, 9, 10}, x = 45

Output: false There is no pair with sum 45.

 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.stream.Collectors;

public class FindPairWithGivenSum {

	public static String findGivenSum(Integer[] arr, int n, int givenSum) {
		int maxPivot = findMaxPivot(arr, 0, n-1, (n-1)/2);
		
		for(int i=maxPivot; i>=0; i--) {
			for(int j=maxPivot+1; j<n; j++) {
				if(arr[i] + arr[j] == givenSum) return new String("("+arr[i]+","+arr[j]+")");
			}
		}
		
		for(int i=maxPivot; i>=0; i--) {
			for(int j=0; j<i; j++)
				if(arr[i] + arr[j] == givenSum) return new String("("+arr[i]+","+arr[j]+")");
		}
		
		for(int i=n-1; i>=maxPivot+2; i--) {
			for(int j=maxPivot+1; j<i; j++)
				if(arr[i] + arr[j] == givenSum) return new String("("+arr[i]+","+arr[j]+")");
		}		
		return null;
	}
	
	public static int findMaxPivot(Integer[] arr, int start, int end, int k)   {
		int _start = start, _end = end, _k = k;
		
		if(arr[_k]>arr[_k+1]) return k;		
		if(arr[_k-1]>arr[_k] && arr[_k+1]>arr[_k]) return _k-1;
				
		if(arr[_start] > arr[_k])
			_end = _k;
		else if(arr[_end] < arr[_k])
			_start = _k;
		else {
			if(arr[_start] > arr[_end]) _end = _k;
			else _start = _k;
		}
		_k = (_start+_end)/2;	
			
		return findMaxPivot(arr, _start, _end, _k);
				
	}
	
	public static int binarySearch(Integer[] arr, int n, int d) {		
		return -1;
	}
	public static void main(String[] args)  {
		StringBuilder stringBuilder = new StringBuilder();
		
		try(BufferedReader bufferedReader = new BufferedReader(
				new InputStreamReader(System.in)))
		{
			int testCase = Integer.parseInt(bufferedReader.readLine());
			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 givenSum = Integer.parseInt(bufferedReader.readLine());
				
				String result = findGivenSum(arr, n, givenSum); 
				if(result !=null) {
					stringBuilder.append("Output: true\n");
					stringBuilder.append("There is a pair " + result + " with sum " + givenSum +"\n");
				} else {
					stringBuilder.append("Output: false\n");
					stringBuilder.append("There is no pair with sum " + givenSum +"\n");
				}
			}
		}		
		catch(IOException ex) {}
		catch(NumberFormatException ex) {}
		
		System.out.println(stringBuilder.toString());
	}

}

---

 예제로 나온 코드

// Java program to find a pair with a given 
// sum in a sorted and rotated array 
class PairInSortedRotated 
{ 
	// This function returns true if arr[0..n-1] 
	// has a pair with sum equals to x. 
	static boolean pairInSortedRotated(int arr[], 
									int n, int x) 
	{ 
		// Find the pivot element 
		int i; 
		for (i = 0; i < n - 1; i++) 
			if (arr[i] > arr[i+1]) 
				break; 
				
		int l = (i + 1) % n; // l is now index of										 
							// smallest element 
						
		int r = i;	 // r is now index of largest 
						//element 
	
		// Keep moving either l or r till they meet 
		while (l != r) 
		{ 
			// If we find a pair with sum x, we 
			// return true 
			if (arr[l] + arr[r] == x) 
				return true; 
	
			// If current pair sum is less, move 
			// to the higher sum 
			if (arr[l] + arr[r] < x) 
				l = (l + 1) % n; 
					
			else // Move to the lower sum side 
				r = (n + r - 1) % n; 
		} 
		return false; 
	} 

	/* Driver program to test above function */
	public static void main (String[] args) 
	{ 
		int arr[] = {11, 15, 6, 8, 9, 10}; 
		int sum = 16; 
		int n = arr.length; 
	
		if (pairInSortedRotated(arr, n, sum)) 
			System.out.print("Array has two elements" + 
							" with sum 16"); 
		else
			System.out.print("Array doesn't have two" + 
							" elements with sum 16 "); 
	} 
} 
/*This code is contributed by Prakriti Gupta*/

또다른 방법

// Java program to find 
// number of pairs with 
// a given sum in a sorted 
// and rotated array. 
import java.io.*; 

class GFG 
{ 
	
// This function returns 
// count of number of pairs 
// with sum equals to x. 
static int pairsInSortedRotated(int arr[], 
								int n, int x) 
{ 
	// Find the pivot element. 
	// Pivot element is largest 
	// element of array. 
	int i; 
	for (i = 0; i < n - 1; i++) 
		if (arr[i] > arr[i + 1]) 
			break; 
	
	// l is index of 
	// smallest element. 
	int l = (i + 1) % n; 
	
	// r is index of 
	// largest element. 
	int r = i; 
	
	// Variable to store 
	// count of number 
	// of pairs. 
	int cnt = 0; 

	// Find sum of pair 
	// formed by arr[l] 
	// and arr[r] and 
	// update l, r and 
	// cnt accordingly. 
	while (l != r) 
	{ 
		// If we find a pair with 
		// sum x, then increment 
		// cnt, move l and r to 
		// next element. 
		if (arr[l] + arr[r] == x) 
		{ 
			cnt++; 
			
			// This condition is required 
			// to be checked, otherwise 
			// l and r will cross each 
			// other and loop will never 
			// terminate. 
			if(l == (r - 1 + n) % n) 
			{ 
				return cnt; 
			} 
			
			l = (l + 1) % n; 
			r = (r - 1 + n) % n; 
		} 

		// If current pair sum 
		// is less, move to 
		// the higher sum side. 
		else if (arr[l] + arr[r] < x) 
			l = (l + 1) % n; 
		
		// If current pair sum 
		// is greater, move 
		// to the lower sum side. 
		else
			r = (n + r - 1) % n; 
	} 
	
	return cnt; 
} 

// Driver Code 
public static void main (String[] args) 
{ 
	int arr[] = {11, 15, 6, 7, 9, 10}; 
	int sum = 16; 
	int n = arr.length; 

	System.out.println( 
			pairsInSortedRotated(arr, n, sum)); 
} 
} 

// This code is contributed by ajit 

결과

---

😒 시간복잡도를 줄이고 싶어서 max값 탐색시, 이진탐색?을 사용하고하였지만.

🤔 흠 givenSum을 찾을때는 경우에 따라서는 O(n!)이 되버리는 것 같다.

🤢 좀 더 시간복잡도와 공간복잡도에 관한 개념을 잡아야지.

😜 정신좀 똑바로 차리고 살아야 겠다.

 

* 위에서 제시한 코드 이외에도 여러 방법이 나와있고, 각각 친절하게 원리와 시간복잡도 및 공간복잡도가 명시되어있으니 필요하면 직접 사이트에서 봐보는것을 추천한다.

www.geeksforgeeks.org/array-rotation/

Program for array rotation - GeeksforGeeks