Merge k Sorted Lists 질문 드립니다.

Question

안녕하세요 강사님.

우선순위 큐 관련 질문 드립니다.

아래 코드와 같이 ListNode 배열 객체인 listNode 를

오름차순으로 설정한 우선순위 큐 에 셋팅(offer) 을 한 후

        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(5);
        
        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(3);
        l2.next.next = new ListNode(4);

        ListNode l3 = new ListNode(2);
        l3.next = new ListNode(6);

        ListNode[] listNode = {l1, l2, l3};
       // ------------중간 생략 ----------------//
        PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(Comp);
        for(ListNode node : lists) {
            if(node != null) {
                pq.offer(node);
            }
            // print(node);
            // System.out.println("1 node.val: " + node.val);
            // System.out.println("1 pq.peek(): " + pq.peek().val);
       }

왜 아래 코드와 같이 다시 offer 를 하는지 궁금합니다.

이미 위 에서 offer 를 했기 때문에 다시 offer 를 하면 중복된 값이 들어가는게 아닌가 하는 생각이 들어서요.

        while(!pq.isEmpty()) {
            ListNode node = pq.poll();
            p.next = node;
            p = p.next;
            if(node.next != null) {
                pq.offer(node.next);
            }
            
            //System.out.println("2 pq.peek(): " + pq.peek().val);
       }

답변 부탁드립니다.

감사합니다.

Answer

안녕하세요~

답변이 늦어 죄송합니다.

pq에 계속 넣어서 heapy를 거치는 과정입니다. pq과 알아서 제일 작은값을 위에다가 올려주는거죠

그걸 새로운 결과값을 저장할 ListNode p를 생성해서 담아주는 과정입니다.

이해가 안되실거 같아서 그림을 그렸습니다.

이 내용도 업데이트 하는과정에 넣도록 하겠습니다. (강의에 존대말을 안쓴부분은 업데이트중입니다)

이해가 안되시면 답글 달아주세요. 절대 부담 갖지마시고 넣어주세요

ListNode, PriotyQueue는 시험에 무조건 나옵니다. 개념 꼭 아셔야 합니다.특히 heapy과정

업데이트중인데 우선순위에 넣도록하겠습니다.

illhumored

Merge k Sorted Lists 질문 드립니다.

질문주신내용

저는 list1 이 통째로 빠진다고 생각했었는데

list1 의 첫 번째 값(1) 만 빠지는 건가요?

illhumored

Merge k Sorted Lists 질문 드립니다.

질문주신내용

저는 list1 이 통째로 빠진다고 생각했었는데

list1 의 첫 번째 값(1) 만 빠지는 건가요?

이 글과 비슷한 Q&A

StringBuilder - 가변 String 질문(강의 말중에서요) + 추가질문

즉시 로딩과 지연 로딩 23분 그림에서 질문있습니다..

@Transactional + @Commit의 의미

lombok의 @ToString이 가지는 이점