[Greedy Algorithm] 결혼식

 

 

설명

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

현수는 결혼식 피로연을 장소를 빌려 3일간 쉬지 않고 하려고 합니다.
피로연에 참석하는 친구들 N명의 참석하는 시간정보를 현수는 친구들에게 미리 요구했습니다.
각 친구들은 자신이 몇 시에 도착해서 몇 시에 떠날 것인지 현수에게 알려주었습니다.
현수는 이 정보를 바탕으로 피로연 장소에 동시에 존재하는 최대 인원수를 구하여 그 인원을 수용할 수 있는 장소를 빌리려고 합니다. 여러분이 현수를 도와주세요.

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

 

 

입력

첫째 줄에 피로연에 참석할 인원수 N(5<=N<=100,000)이 주어집니다.
두 번째 줄부터 N줄에 걸쳐 각 인원의 오는 시간과 가는 시간이 주어집니다.

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

 

 

출력

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

 

 

예시 입력

5
14 18
12 15
15 20
20 30
5 14

 

 

예시 출력

2

 

 

 

풀이

[주의사항]

주의사항은 같은 시간에 한 명이 가고, 한 명이 오는 경우이다. 예를 들어 A가 12시에 와서 14시에 간다고 하고, B가 13시에 와서 14시에 가고, C가 14시에 와서 15시에 간다고 가정해보자. 13시에는 A와 B가 존재한다. 14시에는 A와 B가 가고 C가 오기 때문에 2 - 1 - 1 + 1 = 1 명이 존재한다. 로직 상, 인원 수에 변동이 생길 때 마다 answer의 값을 현재 존재하는 인원 수와 비교하기 때문에 가는 사람을 먼저 카운팅 해야 한다. 그렇지 않은 경우를 살펴보면 다음과 같다. 14시에 C가 먼저 오고 A와 B가 간다고 생각하면 C가 오는 순간 인원 수가 3이 되기 때문에 answer는 3으로 갱신된다. 문제에서, 정각에 가는 사람은 정각에 존재하지 않는다고 했기 때문에 가는 사람을 먼저 카운팅 해야하는 것이다.

 

[로직]

입력받은 Time 객체를 시간상 오름차순 정렬을 하고, 시간이 같다면 알파벳 오름차순('e' -> 's')을 정렬을 한다. 이렇게 하면 같은 시간대에 가거나 오는 사람들의 인원 카운팅 순서는 가는 사람 먼저, 오는 사람 나중에 로 된다.

answer 변수는 정수 중 가장 작은 값으로 초기화 하고, 현재 존재하는 인원인 cnt 변수는 0으로 초기화 한다.

정렬된 Time이 담긴 ArrayList를 돌면서, 상태가 's'인 객체이면 현재 존재하는 인원을 1 증가시키고, 그렇지 않다면 (상태가 'e'이면) 현재 존재하는 인원을 1 감소시킨다. 값이 변경될 때 마다 answer와 현재 존재하는 값을 비교하여 더 큰 값을 넣는다.

 

 

 

코드

package inflearn._9_3;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

class Time implements Comparable<Time> {

    public int time;
    public char state;

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

    @Override
    public int compareTo(Time ob) {
        if(this.time == ob.time) return this.state - ob.state; // 상태 오름차순
        else return this.time-ob.time; // 시간 오름차순
    }
}


public class Main {

    public static int solution(ArrayList<Time> arr) {

        int answer = Integer.MIN_VALUE;

        Collections.sort(arr); // 정렬
        int cnt = 0; // 현재 존재하는 인원

        for(Time ob : arr) {
            if (ob.state == 's') cnt++;
            else cnt--;
            answer = Math.max(answer, cnt);

        }

        return answer;

    }

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        ArrayList<Time> arr = new ArrayList<>();

        StringTokenizer st;

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int startTime = Integer.parseInt(st.nextToken());
            int endTime = Integer.parseInt(st.nextToken());
            arr.add(new Time(startTime, 's'));
            arr.add(new Time(endTime, 'e'));
        }

        bw.write(sb.append(solution(arr)).toString());
        bw.flush();
        bw.close();
        br.close();


    }


}