백준 - 1931

import java.io.*;
import java.util.*;

class Room implements Comparable<Room>{
    int start;
    int end;

    public Room(int start, int end){
        this.start = start;
        this.end = end;
    }
    @Override
    public int compareTo(Room other){
        if(this.end == other.end) return this.start - other.start;
        return this.end - other.end;
    }
}
public class Main{

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        List<Room> list = new ArrayList<>();
        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            list.add(new Room(s,e));
        }
        Collections.sort(list);

        int res = 0;
        int target = 0;
        for(Room r : list){
            if(r.start >= target){
                res++;
                target = r.end;
            }
        }
        System.out.println(res);
    }
}

풀이과정 및 리뷰

• 문제 접근: before의 회의종료 시간과, after의 회의시작 시간을 비교해서 after.start ≥ before.end시간이라면 시간이 겹치지 않고 회의를 배정할 수 있다고 판단했음

  또한, 이렇게 리스트를 비교해나가기 위해선 정렬이 필요하다고 생각했고, 끝나는 시간이 빠른순(테케에 힌트가 있었다..) → 시작시간이 빠른순으로 정렬하여 순회하는것이 제일 효율적

  (처음 삽질)

  end - start의 회의에 걸리는 시간을 기준으로 정렬하여 before.end / after,start를 비교해 겹치지 않는 회의 개수를 카운트 하려고 했음

  Map<Integer,Integer>에 시작 / 종료 시간을 넣어 시작시간기준 제일 빠른 종료시간을 맵에서 갱신해 갯수를 세려고 함

  (문제점) 4/4로 끝나는 경우와 4/5 등이 함께 있을경우 회의시간이 0시간인 회의에 대해++ 해준 후 4/5를 선택해야 하는데, end - start시간이 가장 작은 값만 담아 카운트가 제대로 되지 않음. 그래서 start=end인 회의에 대해 맵에 넣지 않고 무조건 cnt먼저 ++ 해둔후 1이상 차이나는 가장 작은 값만 넣으려 함 → 이랬더니, 해당 시간이 아닌 경우로 회의를 배정했을 때 회의 수가 가장 큰 경우의 처리가 불가능해서 포기
  

• 시간복잡도: $O(N Log N)$

  Collections.sort(list) O(N log N) + 리스트 순회 O(N)
  

• 풀이과정

  • Room 클래스 생성 -Comparable을 구현하여 끝나는 시간(같다면 시작시간) 기준으로 정렬
    
  • 메인에서 리스트 순회하며 target(직전 회의 끝나는시간)과 직후 회의의 시작시간을 비교하여 겹치지 않는 회의수 카운트

• 개선점

compareTo 대신 Comparator 활용

• Comparable을 구현하면 한 가지 기준으로만 정렬됩니다.
• 경우에 따라 다른 기준 정렬을 하고 싶을 땐 Comparator를 쓰는 게 더 유연해요.

list.sort((a, b) -> {
    if (a.end == b.end) return a.start - b.start;
    return a.end - b.end;
});
→ 이렇게 하면 `Room`에 불필요하게 `Comparable`을 구현하지 않아도 됨

Room 클래스 불변성 확보

• start와 end는 회의 시간으로 변경될 일이 없으므로 final로 선언하는 게 안전.

class Room {
    final int start;
    final int end;

    public Room(int start, int end){
        this.start = start;
        this.end = end;
    }
}

정렬 안정성 보장

• 현재 compareTo 구현은 잘 돼 있지만, this.start - other.start 같은 뺄셈 연산은 오버플로우 위험이 있어요. → Integer.compare(this.start, other.start)를 쓰면 안전합니다.
  

list.sort((a, b) -> {
    int cmp = Integer.compare(a.end, b.end);
    if (cmp == 0) return Integer.compare(a.start, b.start);
    return cmp;
});

기타

Java에서 Collections.sort() 동작 방식

• Collections.sort(List<T> list) → 내부적으로 list.toArray()를 호출해서 배열로 바꾼 다음, Arrays.sort()를 실행
  
• 따라서 실제 정렬 알고리즘은 Arrays.sort()가 무엇을 쓰는지에 따라 결정됨

---

✅ 구체적으로

1. Primitive 타입 배열 (int[], double[] 등)
   • Dual-Pivot Quicksort (이중 피벗 퀵정렬) 사용
   • 시간 복잡도: 평균 O(N log N), 최악 O(N²)
   • 다만 구현이 잘 돼 있어서 실제로는 굉장히 빠름
2. 객체 배열 (Integer[], String[], Room[] 등 Comparable 구현 객체)
   • Java 7 이후 → TimSort 사용 (Merge Sort + Insertion Sort를 합친 하이브리드 정렬 알고리즘)
     
   • 시간 복잡도:
     • 최악: O(N log N)
     • 최선(이미 정렬된 경우): O(N)
   • 안정 정렬(Stable Sort) → 같은 값일 경우 기존 순서 유지.
3. 즉, Collections.sort(list)는
   • 내부적으로 list.toArray() → Arrays.sort(Object[]) → TimSort 순서로 동작.
   • 따라서 객체 리스트 정렬은 항상 안정 정렬

---

📌 정리

• Collections.sort(list) → 내부적으로 Arrays.sort() 호출.
• Primitive 배열: Dual-Pivot QuickSort.
• 객체 배열: TimSort (안정 정렬, O(N log N)).
• 실무에서 List 정렬 시 대부분 TimSort

TimSort란?

병합정렬 + 삽입정렬 방법으로, 크기가 작은 배열에서는 삽입정렬을 이용하고 크기가 큰 경우 병합정렬을 사용한다. 그래서 하이브리드 정렬이라고도 부른다.

삽입 정렬 (Insertion Sort)

개념

• 손으로 카드를 정렬하는 방식과 비슷
• 배열을 앞에서부터 순회하며 현재 원소를 알맞은 위치에 끼워 넣는 방식

배열: [5, 2, 4, 6, 1, 3]

1단계: 2 → [2, 5, 4, 6, 1, 3]
2단계: 4 → [2, 4, 5, 6, 1, 3]
3단계: 6 → [2, 4, 5, 6, 1, 3]
4단계: 1 → [1, 2, 4, 5, 6, 3]
5단계: 3 → [1, 2, 3, 4, 5, 6]

병합 정렬 (Merge Sort)

개념

• 분할 정복(Divide and Conquer) 방식
• 배열을 반으로 쪼개고, 각각 정렬 후 병합

배열: [5, 2, 4, 6, 1, 3]

분할: [5, 2, 4] [6, 1, 3]
분할: [5] [2, 4] ... → 재귀적으로 정렬
병합: [2, 4, 5] [1, 3, 6] → 최종 병합 → [1, 2, 3, 4, 5, 6]