정렬

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

오름차순 정렬하기

  • ArrayList를 이용하는 방법
  • 예제 코드
      // 문제 링크 : 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를 이용하는 방법
  • 예제 코드
      // 문제 링크 : 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는 다른 순서로 정렬하고 싶을 때 사용한다.
    • 이를테면 문자열을 길이 순으로 정렬하고 싶을 때 사용한다.