Algorithm Study With Java #3 (JAVA SORT)

정렬

• 배열 정렬
  - Arrays.sort
• 콜렉션 정렬
  - Collections.sort
  

오름차순 정렬하기

• ArrayList를 이용하는 방법
• 예제 코드

  	```Java
  	// 문제 링크 : https://www.acmicpc.net/problem/2750
  	import java.util.*;
  	public class Main {
  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    ArrayList<Integer> a = new ArrayList<Integer>();
    for (int i=0; i<n; i++) {
      int temp = sc.nextInt();
      a.add(temp);
    }
    Collections.sort(a); // Sort ASC
    for (int x : a) {
      System.out.println(x); 
    }
  }

  }

  	```

• Array를 이용하는 방법
• 예제 코드

  	```Java
  	// 문제 링크 : https://www.acmicpc.net/problem/2750
  	import java.util.*;
  	public class Main {
  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] a = new int[n];
    for (int i=0; i<n; i++) {
      int temp = sc.nextInt();
    }
    Arrays.sort(a); // Sort ASC
    for (int x : a) {
      System.out.println(x);
    }
  }

  }

  	```

좌표 정렬하기

• 클래스를 정렬하는 순간 정렬이 조금 어려워짐
• 문제 링크 : boj.kr/11650
• (x, y)가 여러 개 있을 때, x가 증가하는 순으로 정렬하는 문제
  - 하지만 만일 x가 같다면 y가 증가하는 순서로 정렬하는 문제
• Comparator나 Comparable을 작성해야 한다.
  - 하지만 둘 다 작성할 필요는 없다.
  - 둘 중 하나만 작성하면 된다.
• Comparable의 구현
  - java.lang.Comparable< T>
  - Comparable은 compareTo 메소드를 작성하면 된다.
• compareTo의 구현
  • 작성 예제

    			public int compareTo(Point that) {
      if (this.x < that.x) {
        return -1; 
      } else if (this.x == that.x) {
        if (this.y < that.y) {
          return -1; 
        } else if (this.y == that.y) {
          return 0; 
        } else {
          return 1; 
        }
      } else {
        return 1; 
      }
    }
    			// this가 작으면 -1
    // this와 같으면 0
    // this가 크면 1

    		- 구현의 주의점
    - sgn(x.compareTo(y)) == -sgn(y.compareTo(x))
    	- sgn은 부호를 의미함
        - x를 y로 비교했을 때의 부호는, y를 x로 비교했을 때의 부호와 같아야 함
    - x.compareTo(y) > 0 && y.compareTo(z)>0 implies x.compareTo(z) > 0
    	- x > y > z의 의미
    - x.compareTo(y) == 0 implies that sgn(x.compareTo(z)) == sgn(y.compareTo(z))
    	- x = y일 때, z와 x를 비교한 것과 z와 y를 비교한 것은 같음
    - 이 조건을 위배하면 자바는 프로그램을 종료시킴

• Comparator의 구현
  - java.util.Comparator< T>

  		Arrays.sort(a, new Comparator<Point>() {
    public int compare(point p1, point p2) {
      return p1.compareTo(p2);  
    }
  });
  		```
  - 2번째 인자로 어떻게 compare할 것인지를 결정하는 Comparator 함수를 넣으면 됨

• 예제 코드 1 Comparable
  - 따로 sort method를 구현할 필요가 없다.

	import java.util.*;
	import java.io.*;
	class Point implements Comparable<Point> {
        int x, y;
        Point(int x, int y) {
          this.x = x;
          this.y = y;
        }
        public int compareTo(Point that) {
          if (this.x < that.x) {
            return -1; 
          } else if (this.x == that.x) {
            if (this.y < that.y) {
              return -1; 
            } else if (this.y == that.y) {
              return 0;
            } else {
              return 1;
            }
          } else {
              return 1; 
          }
        }
    }

• 예제 코드 2 Comparator
  • sort method 2번째 인자로 어떻게 정렬할 것인지를 넣어주는 과정이 필요

    Arrays.sort(a, new Comparator<Point>() {
      public int compare(Point p1, Point p2) {
        return p1.compareTo(p2); 
      }
    });

    		- 예제 문제로는 11650, 11651이 있다.
    		- 참고) Comparator Lambda로 구현하기

     Comparator<Point> comparator = (p1, p2) -> {
       if(p1.y > p2.y) {
         return 1;
       }
       else if(p2.y > p1.y) {
         return -1;
       }
       else if(p1.y == p2.y){
         if(p1.x > p2.x){
           return 1;
         }
         else if(p2.x > p1.x){
           return -1;
         }
         else{
           return 0;
         }
       }
       return 1;
     };

Comparable과 Comparator의 의미

• Comparable은 compareTo를 구현하는데, natural순서를 정의한다.
  - natural순서란 이를테면 문자열의 사전순과 같은 정석적인 순서를 의미한다.
• Comparator는 다른 순서로 정렬하고 싶을 때 사용한다.
  - 이를테면 문자열을 길이 순으로 정렬하고 싶을 때 사용한다.