0%

[JAVA] 프로그래밍 대회에서 사용하는 자바 - 3

작성일 Edited on In Disqus:

백준 강의 정리 - 정렬

  • 배열은 Arrays.sort, 콜렉션은 Collections.sort를 사용한다.

목차

  1. 오름차순 정렬

  2. 좌표 정렬하기

  3. 좌표 정렬하기 2

1. 오름차순 정렬

1.1 ArrayList를 이용하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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>();
    // n개의 수를 입력받아 저장
    for (int i=0; i<n; i++) {
      int temp = sc.nextInt();
      a.add(temp);
    }

    // ArrayList에 있는 모든 요소를 오름차순으로 정렬
    Collections.sort(a);

    //출력
    for (int x : a) {
      System.out.println(x);
    }
  }
}

1.2 정수 배열을 이용하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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++) {
      a[i] = sc.nextInt();
    }

    // 정렬
    Arrays.sort(a);

    // 출력
    for (int x : a) {
      System.out.println(x);
    }
  }
}

2. 좌표 정렬하기

  • (x,y)가 여러 개 있을 때, x가 증가하는 순으로, 같으면 y가 증가하는 순으로 정렬하는 문제.
  • Comparator나 Comparable을 작성해야 한다.
  • Comparable는 compareTo를 구현하는데, 내츄럴한 순서를 정의한다. (예를 들면 문자열은 사진 순)
  • Comparator는 다른 순서로 정렬하고 싶을 때 사용한다. (예를 들면 문자열을 길이 순으로 정렬하고 싶을 때)

2.1 Comparable

CompareTo를 작성할 때는 조심해야 할 것이 세 가지가 있다. CompareTo를 작성할 때는 이 세 가지 조건을 전부 만족해야 한다. 만약 세 가지 중 하나에 위배되는 경우 정렬을 계속하지 않고 프로그램의 실행을 중지하게 된다. (런타임 에러)

  1. sgn(x.compareTo(y)) == -sgn(y.compareTo(x))
    • 여기서 sgn은 부호를 나타낸다. x를 y를 서로 비교했을 때 부호가 서로 같아야 한다.
  2. x.compareTo(y)>0 && y.compareTo(z)>0) implies x.compareTo(z)>0
    • x랑 y를 비교했을 때 양수고, y랑 z를 비교했을 때 양수라면 x랑 z를 비교했을 때도 양수가 나와야 한다.
  3. x.compareTo(y)==0 implies that sgn(x.compareTo(z)) == sgn(y.compareTo(z))
    • x와 y가 같다면, x를 z랑비교한 것, 그리고 y를 z에 비교한 것의 부호가 서로 같아야 한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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; 
  }
}

좌표 정렬하기 문제 풀어보기 - Comparable

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.*;
import java.io.*;

// Comparable implement 하기
class Point implements Comparable<Point> {
  int x, y;
  Point(int x, int y) {
    this.x = x;
    this.y = y;
  }

  // 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;
    }
  }
}
public class Main {
  public static void main(String args[]) throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(bf.readLine());
    Point[] a = new Point[n];
    for (int i=0; i<n; i++) {
      String[] temp = bf.readLine().split(" ");
      int x = Integer.parseInt(temp[0]);
      int y = Integer.parseInt(temp[1]);

      // 알아서 정렬이 된다.
      a[i] = new Point(x, y);
    }
    Arrays.sort(a);
    StringBuilder sb = new StringBuilder();
    for (Point p : a) {
      sb.append(p.x + " " + p.y + "\n");
    }
    System.out.print(sb);
  }
}

2.2 Comparator

두 번째 인자로 어떻게 compare할지를 나타내는 함수를 넣어놓으면 된다.

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

좌표 정렬하기 문제 풀어보기 - Comparator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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;
    }
  }
}
public class Main {
  public static void main(String args[]) throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(bf.readLine());
    Point[] a = new Point[n];
    for (int i=0; i<n; i++) {
      String[] temp = bf.readLine().split(" ");
      int x = Integer.parseInt(temp[0]);
      int y = Integer.parseInt(temp[1]);
      a[i] = new Point(x, y);
    }

    // sort메소드에 어떻게 정렬할 건지를 두 번째 인자로 넣어주면 된다.
    Arrays.sort(a, new Comparator<Point>() {
      public int compare(Point p1, Point p2) {
        return p1.compareTo(p2);
      }
    });
    StringBuilder sb = new StringBuilder();
    for (Point p : a) {
      sb.append(p.x + " " + p.y + "\n");
    }
    System.out.print(sb);
  }
}

3. 좌표 정렬하기 2

  • (x,y)가 여러 개 있을 때, y가 증가하는 순으로, 같으면 x가 증가하는 순으로 정렬하는 문제.
  • Comparator를 사용해야 의미적으로 올바른 구현을 할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
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;
    }
  }
}
public class Main {
  public static void main(String args[]) throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(bf.readLine());
    Point[] a = new Point[n];
    for (int i=0; i<n; i++) {
      String[] temp = bf.readLine().split(" ");
      int x = Integer.parseInt(temp[0]);
      int y = Integer.parseInt(temp[1]);
      a[i] = new Point(x, y);
    }
    Arrays.sort(a, new Comparator<Point>() {
      public int compare(Point p1, Point p2) {
        if (p1.y < p2.y) {
          return -1;
        } else if (p1.y == p2.y) {
          if (p1.x < p2.x) {
            return -1;
          } else if (p1.x == p2.x) {
            return 0;
          } else {
            return 1;
          }
        } else {
          return 1;
        }
      }
    });
    StringBuilder sb = new StringBuilder();
    for (Point p : a) {
      sb.append(p.x + " " + p.y + "\n");
    }
    System.out.print(sb);
  }
}