zoaseo
To Infinity And Beyond
zoaseo
전체 방문자
오늘
어제
  • 분류 전체보기 (763)
    • 개발이 좋아서 (381)
      • SAP가 좋아서 (3)
      • Java가 좋아서 (42)
      • Spring이 좋아서 (50)
      • JPA가 좋아서 (0)
      • QueryDSL이 좋아서 (26)
      • Docker가 좋아서 (7)
      • Redis가 좋아서 (7)
      • AWS가 좋아서 (5)
      • CI/CD가 좋아서 (6)
      • Troubleshooting이 좋아서 (4)
      • Kotlin이 좋아서 (7)
      • SQL이 좋아서 (6)
      • HTTP가 좋아서 (21)
      • JavaScript가 좋아서 (30)
      • TypeScript가 좋아서 (6)
      • Vue가 좋아서 (21)
      • Flutter가 좋아서 (61)
      • React가 좋아서 (20)
      • Redux(React)가 좋아서 (2)
      • Angular가 좋아서 (22)
      • HTML이 좋아서 (9)
      • CSS가 좋아서 (15)
      • PHP가 좋아서 (9)
      • Illustrator가 좋아서 (2)
    • 노력이 좋아서 (169)
    • 결과물이 좋아서 (14)
    • 코딩연습이 좋아서 (168)
      • 이론이 좋아서 (62)
      • SQL이 좋아서 (90)
    • 유용한 사이트가 좋아서 (28)
    • Github (2)

인기 글

티스토리

hELLO · Designed By 정상우.
zoaseo

To Infinity And Beyond

코딩연습이 좋아서/이론이 좋아서

Greedy Algorithm - 결혼식

2024. 12. 18. 20:39

설명

현수는 다음 달에 결혼을 합니다.

현수는 결혼식 피로연을 장소를 빌려 3일간 쉬지 않고 하려고 합니다.

피로연에 참석하는 친구들 N명의 참석하는 시간정보를 현수는 친구들에게 미리 요구했습니다.

각 친구들은 자신이 몇 시에 도착해서 몇 시에 떠날 것인지 현수에게 알려주었습니다.

현수는 이 정보를 바탕으로 피로연 장소에 동시에 존재하는 최대 인원수를 구하여 그 인원을 수용할 수 있는 장소를 빌리려고 합니다. 여러분이 현수를 도와주세요.

만약 한 친구가 오는 시간 13, 가는시간 15라면 이 친구는 13시 정각에 피로연 장에 존재하는 것이고 15시 정각에는 존재하지 않는다고 가정합니다.

입력

첫째 줄에 피로연에 참석할 인원수 N(5<=N<=100,000)이 주어집니다.

두 번째 줄부터 N줄에 걸쳐 각 인원의 오는 시간과 가는 시간이 주어집니다.

시간은 첫날 0시를 0으로 해서 마지막날 밤 12시를 72로 하는 타임라인으로 오는 시간과 가는 시간이 음이 아닌 정수로 표현됩니다.

출력

첫째 줄에 피로연장에 동시에 존재하는 최대 인원을 출력하세요.

예시 입력 1 

5
14 18
12 15
15 20
20 30
5 14

예시 출력 1

2

 

import java.util.*;

class Time implements Comparable<Time> {
    int time;
    char state;

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

    @Override
    public int compareTo(Time t) {
        if (this.time == t.time) return this.state - t.state;
        else return this.time - t.time;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        List<Time> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int sT = sc.nextInt();
            int eT = sc.nextInt();
            list.add(new Time(sT, 's'));
            list.add(new Time(eT, 'e'));
        }

        Collections.sort(list);

        int cnt = 0;
        int answer = 0;
        for (Time time : list) {
            if (time.state == 'e') {
                cnt--;
            } else {
                cnt++;
            }
            answer = Math.max(cnt, answer);
        }

        System.out.println(answer);
    }
}

- 상태를 오름차순하여 'e' 가 's' 보다 먼저 정렬해서 'e'면 바로 빼주어야 나가는 시간 정각에 인원이 추가로 계산되지 않는다.

'코딩연습이 좋아서 > 이론이 좋아서' 카테고리의 다른 글

Greedy Algorithm - 친구인가? (Disjoint-Set : Union&Find)  (2) 2024.12.18
Greedy Algorithm - 최대 수입 스케줄(PriorityQueue)  (0) 2024.12.18
Greedy Algorithm - 회의실 배정  (0) 2024.12.18
Greedy Algorithm - 씨름 선수  (1) 2024.12.18
DFS, BFS 활용 - 피자 배달 거리(삼성 SW역량평가 기출문제 : DFS활용)  (1) 2024.12.16

    티스토리툴바