Arrays.sort()
- 배열을 정렬할 때 사용한다.
- DualPivotQuicksort 사용
- 평균 O(nlogn)
- 최악 O(n^2)
Collections.sort()
- 리스트를 정렬할 때 사용한다.
- Timesort 사용 : 삽입 정렬 + 합병 정렬
- 평균 O(nlogn)
- 최악 O(nlogn)
1차원 배열 정렬
문자열 배열
- 오름차순 정렬
Arrays.sort(arr);
Collections.sort(list);
- 내림차순 정렬 : 정렬 후에 반대로 뒤집어 준다.
Arrays.sort(arr, Comparator.reverseOrder());
Collections.sort(list, Collections.reverseOrder());
정수형 배열
- Object이 아닌 primitive타입 자료형 이기 때문에 Comparator를 사용해 정렬 불가능
- 오름차순 정렬 -> 뒤집기
// 오름차순 정렬
Arrays.sort(arr);
// 내림차순 정렬
Arrays.sort(arr); // 오름차순 정렬 후
for(int i=0; i<arr.length/2; i++){ // 순서를 뒤집어준다.
int temp = arr[i];
arr[i] = arr[arr.length-i-1];
arr[arr.length-i-1] = temp;
}
- 리스트 : Collections.sort() 사용
Collections.sort(list);
Collections.sort(list, Collections.reverseOrder());
2차원 배열
// 첫번째 원소 오름차순
Arrays.sort(arr, (o1, o2)->{
return o1[0]-o2[0];
});
// 첫번째 원소 내림차순
Arrays.sort(arr, (o2, o1)->{
return o1[0]-o2[0];
});
// 두번째 원소 오름차순
Arrays.sort(arr, (o1, o2)->{
return o1[1]-o2[1];
});
// 두번째 원소 내림차순
Arrays.sort(arr, (o2, o1)->{
return o1[1]-o2[1];
});
CompareTo - 정렬에 조건 넣기
class Point implements Comparable<Point>{
public int x, y;
Point(int x, int y){
this.x=x;
this.y=y;
}
@Override
public int compareTo(Point o){
if(this.x==o.x){ // x 값이 같을 경우
return this.y-o.y;
} else {
return this.x - o.x;
}
}
}
CompareTo - 씨름선수
키와 몸무게 모두 높은 지원자가 존재하면 해당 지원자는 탈락
키를 먼저 내림차순으로 정렬해주고 몸무게를 비교한다.
class Body implements Comparable<Body>{
public int h, w;
Body(int h, int w){
this.h = h;
this.w = w;
}
@Override
public int compareTo(Body o){ // h 내림차순
return o.h-this.h;
}
}
public class Solution {
public static int solution(ArrayList<Body> arr, int n){
int answer = 0;
Collections.sort(arr); // 내림차순
int max = Integer.MIN_VALUE;
for(Body ob : arr){
if(ob.w>max){
max = ob.w;
answer++;
}
}
return answer;
}
public static void main(String[] args) {
Solution T = new Solution();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
ArrayList<Body> arr = new ArrayList<>();
for(int i=0; i<n; i++){
int height = sc.nextInt();
int weight = sc.nextInt();
arr.add(new Body(height, weight));
}
System.out.println(T.solution(arr, n));
}
}
- 1개의 회의실에서 n개의 회의를 할 때
- 시간이 겹치지 않게 최대 수의 회의 찾기
- 시작 시간과 끝나는 시간이 주어진다.
- 끝나는 시간을 오름차순 해준다.
- 끝나는 시간이 같으면 시간순으로 오름차순한다.
class Time implements Comparable<Time> {
public int s, e; // 시작시간, 끝나는시간
Time(int s, int e){
this.s = s;
this.e = e;
}
@Override
public int compareTo(Time o){
if(this.e==o.e){ // 끝나는시간이 같으면 시간순으로 오름차순
return this.s-o.s; // 오름차순
} else {
return this.e-o.e;
}
}
}
public class Solution {
public int solution(ArrayList<Time> arr, int n){
int count=0;
Collections.sort(arr);
int et = 0;
for(Time ob : arr){
if(ob.s>=et){
count++;
et = ob.e;
}
}
return count;
}
public static void main(String[] args) {
Solution T = new Solution();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
ArrayList<Time> arr = new ArrayList<>();
for(int i=0; i<n; i++){
int meet = sc.nextInt();
int room = sc.nextInt();
arr.add(new Time(meet, room));
}
System.out.println(T.solution(arr, n));
}
}