섹션 9 Greedy - 3. 결혼식

문제 설명

현수는 3일 동안 피로연을 열 예정이다.
친구 N명의 도착 시간과 퇴장 시간이 주어진다.
현수는 동시에 피로연장에 가장 많이 모이는 인원 수를 알고 싶어 한다.

한 사람이 13시에 도착해서 15시에 떠난다면
13시는 포함, 15시는 포함하지 않음
즉, [13, 15) 구간에 해당

---

입력 & 출력

입력

5
14 18
12 15
15 20
20 30
5 14

 

출력

2

---

해결 방법

이 문제는 전형적인 "이벤트 정렬 후 스위핑(sweep line)" 문제다.

• 모든 도착/퇴장 이벤트를 하나의 리스트에 저장
• 시간순 정렬한 뒤에, 순서대로 이벤트를 보며 현재 인원 수를 누적 계산
• 최대 인원이 나타난 시점을 찾아낸다

단, 같은 시각에 도착과 퇴장이 겹치면
퇴장을 먼저 처리해야 정확한 인원이 계산된다.

---

전체 코드

import java.util.*;

class Time implements Comparable<Time> {
    int time;
    char state;
    Time(int time, char state) {
        this.time = time;
        this.state = state;
    }

    @Override
    public int compareTo(Time o) {
        if (this.time == o.time) return this.state - o.state; // 'e'가 's'보다 먼저
        return this.time - o.time;
    }
}

public class Problem3 {
    public int solution(ArrayList<Time> arr) {
        Collections.sort(arr);
        int answer = 0, count = 0;
        for (Time t : arr) {
            if (t.state == 's') count++;
            else count--;
            answer = Math.max(answer, count);
        }
        return answer;
    }

    public static void main(String[] args) {
        Problem3 T = new Problem3();
        Scanner sc = new Scanner(System.in);
        ArrayList<Time> arr = new ArrayList<>();
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();
            arr.add(new Time(s, 's'));
            arr.add(new Time(e, 'e'));
        }
        System.out.print(T.solution(arr));
        sc.close();
    }
}

---

코드 설명

Time 클래스

class Time implements Comparable<Time> {
    int time;
    char state; // 's': 도착, 'e': 퇴장

    Time(int time, char state) {
        this.time = time;
        this.state = state;
    }

    @Override
    public int compareTo(Time o) {
        if (this.time == o.time) return this.state - o.state; // 'e' < 's'
        return this.time - o.time;
    }
}

• 시간 기준 오름차순 정렬
• 시간이 같으면 'e'(퇴장)를 먼저 처리해야 하므로
  'e' - 's' → 음수 → 'e'가 먼저 정렬됨

정렬 결과 예시

입력: [14 's'], [14 'e']
정렬 후: [14 'e'], [14 's']
→ 14시에 나가는 사람을 먼저 처리해야 1명만 있다고 계산됨

---

시간 복잡도

• 도착/퇴장 합치기 : O(N)
• 정렬 (2N개의 이벤트) : O(N log N)
• 순회하며 계산 : O(N)

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런