IM

작지만 단단하게

Greedy기출문제 풀이

결혼식

  • 설명 : 현수는 다음 달에 결혼을 합니다. 현수는 결혼식 피로연을 장소를 빌려 3일간 쉬지 않고 하려고 합니다.

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

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

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

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

  • 입력 : 첫째 줄에 피로연에 참석할 인원수 N(5<=N<=100,000)이 주어집니다. 두 번째 줄부터 N줄에 걸쳐 각 인원의 오는 시간과 가는 시간이 주어집니다. 시간은 첫날 0시를 0으로 해서 마지막날 밤 12시를 72로 하는 타임라인으로 오는 시간과 가는 시간이 음이 아닌 정수로 표현됩니다.

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

  • 풀이 답안

import java.util.*;

class Invite implements Comparable<Invite> {
    int time;
    int state;

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

    @Override
    public int compareTo(Invite o) {
        return (this.time!=o.time) ? this.time-o.time : this.state-o.state;
    }
}

public class Main {

    public void solution(List<Invite> list) {
        int answer = 0;
        int crr = 0;
        for(int i=0; i<list.size(); i++){
            if(list.get(i).state==0) crr--;
            else crr++;
            answer = Math.max(answer, crr);
        }
        System.out.println(answer);
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner scan = new Scanner(System.in);
        int num = scan.nextInt();
        List<Invite> list = new ArrayList<>();
        for(int i=0; i<num; i++){
            int s = scan.nextInt();
            list.add(new Invite(s,1));
            int e = scan.nextInt();
            list.add(new Invite(e,0));
        }
        Collections.sort(list);
        main.solution(list);
    }
}
  • 정리
    • 입력 객체를 상태값(입장,퇴장)과 시간의 데이터를 담는 객체로 다시 만든다
    • 시간순으로 정렬하되 동일한 시간대에 이벤트가 발생한다면 나가는 사람 먼저 체크(나가는 시간은 미만, 입장시간은 이상이기 때문에 나가는사람이 먼저 체크 되어야 함)
    • 총 인원을 담을 변수를 만들어주고 시간순으로 정렬된 리스트 반복을 돌면서 상태가 입장이면 1증가, 퇴장이면 1감소

Updated: