inflearn logo
강의

강의
N
챌린지

챌린지
멘토링

멘토링
N
클립

클립
로드맵

로드맵
지식공유

정말 쉽게 풀어보는 코딩 테스트 top 기본 문제 (with 자바)

Merge k Sorted Lists 질문 드립니다.

220

illhumored

작성한 질문수 11

1

안녕하세요 강사님.

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

아래 코드와 같이 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);
       }

답변 부탁드립니다.

감사합니다.

MergekSortedLists java 코테 준비 같이 해요!

답변 1

0

푸샵맨 코딩스터디

안녕하세요~

답변이 늦어 죄송합니다.

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

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

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

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

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

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

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

 

0

illhumored

네 강사님. 답변 감사합니다.

답변 주신 내용에서 궁금한 내용이 있어서요.

Q1. 첫 번 째 스텝(답변의 2번 단계) queue.poll() 을 했을 경우 

list1 이 맨 위에 위치하여 list 1의 뽑아지는것은 이해했는데요.

poll 전 > 

ListNode list 1 = 1 -> 4 -> 5

poll 후 >

ListNode list 1 = 4 -> 5

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

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

0

푸샵맨 코딩스터디

안녕하세요~

질문을 지금 봤네요(제가 답변한 글에 질문이 달리면  표시가 저한테는 안오네요 ㅜㅜ)

질문주신내용

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

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

네 통째로 다 빠지는게 아니고 1만 빠집니다. 그 상태에서 pq에 다시 넣잖아요

1-4-5에서 1일 빼버리고 4-5를 넣는겁니다.

많은분들이 헷갈리시는게 1-4-5, 4-5 둘다 타입이 ListNode입니다.

ListNode안에 next로 다시 넘어가서 그렇지 타입 자체가 ListNode입니다.

이걸 헷갈려서 그러실거여요..그래서 제가 강의에서 그림을 잘 보시면 하나 빼고 

next로 넘기는데 그 타입들이 ListNode입니다. 디버깅을 잘 해보세요

질문을 지금 봤네요(제가 답변한 글에 질문이 달리면 표시가 저한테는 안오네요 ㅜㅜ)

질문주신내용

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

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

네 통째로 다 빠지는게 아니고 1만 빠집니다. 그 상태에서 pq에 다시 넣잖아요

1-4-5에서 1일 빼버리고 4-5를 넣는겁니다.

많은분들이 헷갈리시는게 1-4-5, 4-5 둘다 타입이 ListNode입니다.

ListNode안에 next로 다시 넘어가서 그렇지 타입 자체가 ListNode입니다.

이걸 헷갈려서 그러실거여요..그래서 제가 강의에서 그림을 잘 보시면 하나 빼고 

next로 넘기는데 그 타입들이 ListNode입니다. 디버깅을 잘 해보세요

단위가 ListNode니까 pq에서 다시 heapy과정을 거치면서 오름차순으로 해주면서 빼주는거죠

강의자료에 나오는 m과 n의 범위가 코딩하고 다른거 같습니다

0

252

0

나선형매트릭스 깃허브에 코드가 없는것같아요

0

206

0

로그 파일의 데이터 재정렬 코드가 깃허브에 없어요!

0

220

0

새로 생긴 기초강의 질문드려요

1

372

1

질문드립니다

1

218

1

Unique Paths Integer 질문입니다

0

217

1

subString 방법으로 문제 풀이 영상은 짤린건가요?

1

250

1

DFS 방식으로 푼 것이 맞나요?

0

305

2

질문드립니다~

0

194

1

left if문에 대해서

1

253

1

오타 인가요?

1

235

1

안녕하세요 강사님

1

186

1

질문 드립니다

0

170

2

Queue&Stack 문제해설집 문의

0

182

1

문제분석 로직 질문

1

227

1

시간 복잡도 문의드립니다.

1

229

1

시간복잡도 질문드립니다.

1

199

1

for-each 문 질문있습니다!

0

292

1

강의영상에서 사용된 로그 메소드가 궁금합니다.

2

279

2

강의자료 + 문제 이해 관련 질문입니다

1

276

3

강사님 오류맞나요?

1

204

1

강사님 시간 복잡도에 대해서 질문드립니다.

1

170

1

질문입니다.

1

200

1

문제에 대한 이해

1

312

1