아래와 같은 배열에서 2개를 더해 target을 만들어내는 조합을 뽑아내라.
int[] nums ={7,8,9,2,4,5,1,3,6};
int target =10;
*이중 for문으로 구할 수 있으나 시간복잡도가 높다.
Arrays.sort(nums); // 여기서 투포인터 알고리즘을 활용하기 위해서는 오름차순으로 정렬을 해놓아야한다.
//{1,2,3,4,5,6,7,8,9}
int start =0;
int end = nums.length-1;
while(start<end){ //정렬된 배열이므로 start와 end가 교체하게 되면 중복탐색이 일어난다.
//(start는 0인덱스부터시작해 오른쪽으로 탐색해들어가고, end인덱스는 끝에서 시작해 왼쪽으로 탐색해 들어가므로
if(nums[start]+nums[end]==target){
System.out.println(nums[start] + " " + nums[end]);
end++;
//이때는 end++대신 start++를 해도 괜찮다
} else if(nums[start]+nums[end]<k){
start++;
} else{ //합>k
end--;
}
->정렬된 배열에서 포인터는 일관된 움직임을 가지고 가는게 중요하다.
예를 들어 nums[start]+nums[end]<k일 때 합을 키우기 위해서 end++를 할 수도 있지만
현재 탐색에서는 end는 끝에서부터 왼쪽으로 움직이는 방향성을 가지고 있다.
합>k 일때도, start--를 해서 합을 줄일 수 있지만 start는 오른쪽으로 탐색하는 방향성을 가지고 있고
start--를 하면 이미 지나온 곳을 중복탐색하는 비효율이 발생한다.
Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.
int n= 15;
int[] arr = new int[n+1]; //그래야 15번 인덱스까지 생기니까
for(int i=1 i<n+1; i++){
arr[i] = i;}
int start =1; //문제에서 자연수의 합이니까 시작지점은 1
int end =1; //연속된 수열의 합이니까 시작지점과 끝지점을 같게한후 끝지점을 늘려가면서 탐색
int sum = arr[1]; // 현재지점start~end가 1에만 있으니까 수열의 합은 arr[1]이다.
int count=0;
while(start<=end && end<arr.lengh){ //start가 end를 초과하면 탐색종료. 길이가 1인 수열도 탐색해야하니까
//start==end일 때도 탐색해야함. 또한end가 마지막 인덱스를 넘어가면 탐색종료
if(sum == n){ //수열의 합이 n과 같은 경우의수를 찾는 거니까 count++해준다
sum-=arr[start]; //그리고 계속 탐색을 이어갈 수 있게 start값을 오른쪽으로 이동해주는데
start++; //이동하면 현재의 start값을 sum에서 빼야하기 때문에 먼저 뺀 다음 start++;처리
count++;
} else if(sum <n){ //합이 n보다 작다면 합을 늘리기위해 탐색구간을 늘려야하므로 end++
end++
sum += arr[end];
} else{ //sum>n일 때임 //합이 n보다 크다면 합을 줄여야하므로 탐색구간을 줄여야한다. 그러므로
sum-= arr[start]; // start를 오른쪽으로 옮긴다.
start++; //탐색구간을 줄인다고 end--하지않는 이유는 현재 end가 왼쪽으로 이동하면 중복탐색의 비효율성이 발생
//그리고 여기서 start와 end는 항상 오른쪽으로만 이동하는 일관성을 가지고 있기 때
}
}