인프런 커뮤니티 질문&답변

import java.util.*;

class Marry implements Comparable<Marry>{
        public int s;
        public int e;

        public Marry(int s, int e){
            this.s = s;
            this.e = e;
        }

        @Override
        public int compareTo(Marry o){
            if(this.s == o.s) return this.e - o.e;
            else return this.s - o.s;
        }
    }

public class 결혼식 {

    public int solution(Marry[] slot, int n){
        int answer = 1;

        PriorityQueue<Integer> Q = new PriorityQueue<>();

        Q.offer(slot[0].e);

        for(int i = 1; i < n; i++){
            while(Q.peek() <= slot[i].s) {
                Q.poll();
            }

            Q.offer(slot[i].e);
            answer = Math.max(answer, Q.size());
        }

        return answer;
    }

    public static void main(String[] args) {
        결혼식 T = new 결혼식();
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();

//        ArrayList<Marry> arr = new ArrayList<>();

        Marry[] slots = new Marry[n];

        for(int i = 0; i < n; i++){
            int s = in.nextInt();
            int e = in.nextInt();
            slots[i] = new Marry(s, e);
        }

        Arrays.sort(slots);

        System.out.println(T.solution(slots, n));
    }
}

도착 시간이 현재 인덱스의 시작 시간보다 작거나 같을 때 해당하는 Q를 poll() 해주는 방식으로 처리했습니다.

사실 저는 PriorityQueue가 아니라 그냥 Queue로 풀었는데, 둘이 결과가 상이합니다.

PriorityQueue로 풀었을 때는 정답 값이 나오는데
그냥 Queue로 풀었을 때는 틀린 값이 나옵니다.

PriorityQueue는 우선순위 값을 먼저 반환한다는 차이가 있다는데,

Queue를 사용해도 시작 시간 s 값이 같을 경우 e를 오름차순으로 설정해줬기 때문에

e가 작은 값부터 출력이 되어서 정답 값이 나와야 한다고 생각하는데 아니네요..

계속 짱구를 굴려보는데 이유를 모르겠습니다...

긴글이지만 강사님 도와주십쇼!


+ 추가 )

Queue로는 해결이 안되었던 이유를 이제야 알 것 같습니다..

피로연에 도착한 시간 s 값이 0일 때 나가는 시간 e가 76이라고 가정해보고,

다른 하객은 s 값이 75이고, 나가는 시간 e가 76일 때

Queue로 구현하여 FIFO 방식으로 처리하게 되면

도착 시간 s 를 오름차순으로 정렬하기 때문에

0 1

0 1

...

0 76

과 같이 Q에 저장될 것이고

s = 76이 되었을 때

s = 0 , e = 76인 값만 데이터가 삭제되고,

s = 75, e = 76인 값은 데이터가 삭제되지 않는 문제가 발생하게 됩니다.

하지만 PriorityQueue로 구현하게 되면

e 값이 76인 모든 데이터를 삭제할 수 있게 되므로 이러한 문제를 해결할 수 있게 됩니다.

혹시 맞나요..?