[시뮬레이션]최근접쌍

<문제>

첫번째 아이디어 : O(n^2) 모든 점에 대해서 모두 거리를 구해서 최소 값을 찾는다. 최소값이 여러번 나올 경우 카운트 업. -->시간초과

두번째 아이디어 : 점들을 x좌표로 정렬해준후 , 자신과 가장 근접해있는 다른집합의 점과 만나면 멈춰서 길이를 구해서 비교 -->시간초과

세번째 아이디어 : 생각해보니 왼쪽은 이미 최소가 구해져있어서 오른쪽으로만 최소값들을 계산해주면 되었다. -->시간초과

네번째 아이디어 : 같은 집합이 연달아 붙어있으면 작은 x좌표 집합은 버리고 큰쪽에서 시작해준다. -->시간초과

결과 : 시간초과로 인한 실패

느낀점 : 알고리즘을 구현할 때, 무턱대고 작성하는것은 매우 비효율적이다. 스스로 시뮬레이션을 많이 돌려보면서 최적의 방법를 찾아서

구현하는것이 중요하다. 이때, 시간복잡도가 낮은 방법부터 서서히 최대한 생각해보면서 하는것이 시간적으로도 효율적이다.

**클래스객체의 배열을 위해서 우선순위를 바꿔주는 방법**

항상 할때마다 잊어버리기 때문에 정리해야겠다.

1.해당 클래스에 Comparable<?>을 implements 해준다. ( ? implements Comparable<?> )

2.int compareTo(? x)함수를 만들어서 우선순위를 정해준다. (오버라이딩)

비교하고자 하는 int의 값을 비교해서 오름차순,내림차순을 결정해준다. 

오름차순 : this 가 큰 경우 1을 리턴, this 가 작은 경우 -1을 리턴해준다.

내림차순 : 반대로 해준다. 

import java.util.*;
 
 
 
public class Main { 
 
   static int Y ;
 
 
 
   static class Point implements Comparable<Point>{
 
       int F; 
 
       int x; 
 
       
 
       Point(){}
 
       
 
       Point(int F,int x){
 
           this.F = F;
 
           this.x = x;
 
       }
 
       
 
       public int compareTo(Point p) { 
 
           if(this.x>p.x) return 1;
 
           else if(this.x<p.x) return -1;
 
           else return 0;
 
       }
 
   }
 
   
 
   public static void main(String[] args) {
 
      Scanner scan = new Scanner(System.in);
 
      
 
      int n = scan.nextInt();//ip P number
 
      int m = scan.nextInt();//up Q number
 
      
 
      int py = scan.nextInt();
 
      int qy = scan.nextInt();
 
      Y = py>qy ? py-qy : qy-py;
 
      
 
      Point []XY = new Point[n+m];
 
      for(int i=0;i<n;i++) {
 
          int x = scan.nextInt();
 
          XY[i]=new Point(1,x);
 
      }
 
      
 
      for(int i=n;i<n+m;i++) {
 
          int x = scan.nextInt();
 
          XY[i]=new Point(2,x);
 
      }
 
      
 
      Arrays.sort(XY);
 
      
 
      int count = 0;
 
      int min = Integer.MAX_VALUE;
 
      
 
      int start = 0;
 
      while(true) {
 
          if(XY[start].F==XY[start+1].F) start+=1;
 
          else {
 
              int dis = XY[start+1].x-XY[start].x;
 
              if(min > dis) {
 
                  min = dis;
 
                  count=1;
 
              }else if(min == dis) count++;
 
              start+=1;
 
          }
 
          
 
          if(start==m+n-1) break;
 
      }
 
      
 
      System.out.print(min+Y+" "+count);
 
   }     
 
}