알고리즘 과제 저장1

    // 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!");
       }
       
    }

    댓글