Algorithm Study With Java #3 (JAVA SORT)

jakeseo_me·2019년 2월 12일
0

java algorithm study

목록 보기
3/18

정렬

  • 배열 정렬
    • 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는 다른 순서로 정렬하고 싶을 때 사용한다.
    • 이를테면 문자열을 길이 순으로 정렬하고 싶을 때 사용한다.
profile
대전에 있는 (주) 아이와즈에서 풀스택 웹개발자로 일하고 있는 서진규입니다. 주로 Jake Seo라는 닉네임을 많이 씁니다. Javascript를 좋아합니다.

0개의 댓글