알고리즘 풀다가 막혔습니다..

Question

설명현수는 다음 달에 결혼을 합니다.현수는 결혼식 피로연을 장소를 빌려 3일간 쉬지 않고 하려고 합니다.피로연에 참석하는 친구들 N명의 참석하는 시간정보를 현수는 친구들에게 미리 요구했습니다.각 친구들은 자신이 몇 시에 도착해서 몇 시에 떠날 것인지 현수에게 알려주었습니다.현수는 이 정보를 바탕으로 피로연 장소에 동시에 존재하는 최대 인원수를 구하여 그 인원을 수용할 수 있는 장소를 빌리려고 합니다. 여러분이 현수를 도와주세요.만약 한 친구가 오는 시간 13, 가는시간 15라면 이 친구는 13시 정각에 피로연 장에 존재하는 것이고 15시 정각에는 존재하지 않는다고 가정합니다.입력첫째 줄에 피로연에 참석할 인원수 N(5<=N<=100,000)이 주어집니다.두 번째 줄부터 N줄에 걸쳐 각 인원의 오는 시간과 가는 시간이 주어집니다.시간은 첫날 0시를 0으로 해서 마지막날 밤 12시를 72로 하는 타임라인으로 오는 시간과 가는 시간이 음이 아닌 정수로 표현됩니다.출력예시 입력 15 14 18 12 15 15 20 20 30 5 14예시 출력 12위 문제를package infrenalgorithm.greedy;import java.util.*;class Marry implements Comparable{public int s;public int e;public Marry(int s, int e){this.s = s;this.e = e;}@Overridepublic 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;Queue Q = new LinkedList<>();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 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));}}처음에 위와 같이 코드를 구현했었는데안풀려서 PriorityQueue를 사용했더니 풀리더라고요..PriorityQueue는 우선순위를 먼저 내보낼 수 있다는 점이 Queue와 다른 점이라는데,결과적으로 작은 e 값을 먼저 내보냅니다(poll())그런데 Queue도s를 오름차순으로 두고, s가 같은 값일 때 e를 오름차순으로 두어서작은 e 값을 먼저 내보내는데 왜 둘의 결과가 상이할까요?이유를 모르겠습니다... + 추가 ) Queue로는 해결이 안되었던 이유를 이제야 알 것 같습니다.. 피로연에 도착한 시간 s 값이 0일 때 나가는 시간 e가 76이라고 가정해보고, 다른 하객은 s 값이 75이고, 나가는 시간 e가 76일 때 Queue로 구현하여 FIFO 방식으로 처리하게 되면도착 시간 s 를 오름차순으로 정렬하기 때문에0 10 1...0 76과 같이 Q에 저장될 것이고s = 76이 되었을 때s = 0 , e = 76인 값만 데이터가 삭제되고,s = 75, e = 76인 값은 데이터가 삭제되지 않는 문제가 발생하게 됩니다. 하지만 PriorityQueue로 구현하게 되면 e 값이 76인 모든 데이터를 삭제할 수 있게 되므로 이러한 문제를 해결할 수 있게 됩니다. 혹시 맞나요..?

kiroki · Answer

흠 질문의도와는 다른 얘기지만저라면 int[] people &#61; new int[73];각 item 0으로 초기화해서매시간별 방문자수 배열을 만들고방문자가 5, 30 이면 5,6,7,8,9....29 의 index에 &#43;1씩 하구요제일 마지막에 people에서 최댓값 찾아서 리턴할 것 같네요이러면 얼추 O(n)으로 될 것 같아서요

알고리즘 풀다가 막혔습니다..

1개의 답변

#queue 목록