// PA1
public class findSum{
private int[] S;
public findSum() {
S = null;
}
public findSum(int[] s) {
setArray(s);
}
public void setArray(int[] s) { //수열을 받아 멤버 변수 s에 대입
int i=0, n = s.length;
S = null;
S = new int[n];
for(i=0; i<n; i++) S[i] = s[i];
}
public void showArray() {
int i=0, n = S.length;
for(i=0; i < n;i++) System.out.print(S[i]+ " ");
System.out.println();
}
private void swap(int arr[], int index1, int index2) {
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
private void quick_sort(int[] a, int lo, int hi) {
if(lo >= hi) {
return;
}
int pivot = partition(a, lo, hi);
quick_sort(a, lo, pivot - 1);
quick_sort(a, pivot + 1, hi);
}
private int partition(int[] a, int left, int right) {
int lo = left;
int hi = right;
int pivot = a[left];
while(lo < hi) {
while(a[hi] > pivot && lo < hi) {
hi--;
}
while(a[lo] <= pivot && lo < hi) {
lo++;
}
swap(a, lo, hi);
}
swap(a, left, lo);
return lo;
}
public int find(int x) {
int s_length = S.length;
int temp;
int left = 0;
int right = s_length-1;
quick_sort(S, 0, s_length-1);
while(left < right) {
temp = S[left] + S[right];
if(temp == x) return 1;
else if(temp < x) left++;
else right--;
}
return 0;
}
public static void main(String args[]) {
int[] array = {168, 44, -25, 149, 211, 156, 246, 133, 9, -199};
findSum fs = new findSum(array);
if(fs.find(108) == 1) System.out.println("Exist!");
else System.out.println("Not Exist!");
if(fs.find(107) == 1) System.out.println("Exist!");
else System.out.println("Not Exist!");
}
}
'Algorithm > Problem Solving' 카테고리의 다른 글
알고리즘 과제 저장2 (0) | 2021.11.10 |
---|---|
[Java] 삽입 정렬(insertion sort) (0) | 2021.09.11 |
[Python] SWEA 2019번 : 더블더블 (0) | 2021.08.18 |
[Python] SWEA 2050번 : 알파벳을 숫자로 변환 (0) | 2021.08.18 |
[Python] SWEA 2063번 : 중간값 찾기 (0) | 2021.08.18 |
댓글