99클럽 코테 스터디 8일차 TIL + 정렬/[프로그래머스] H-Index/JAVA 힙풀이

 

 

 

 

 

 

1. 오늘의 학습 키워드

---

 

정렬

자바

최대힙

 

 

 

2. 오늘의 학습 문제 

---

문제

---

 

https://school.programmers.co.kr/learn/courses/30/lessons/42747

프로그래머스

 

 

코드

---

import java.util.*;



class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()); //최대힙선언

        for(int citation : citations)
            pq.add(citation);
        
        int h= 0; //h번 이상 인용된 논문 개수를 센다.  
        //  n>=h이다. 
        
        while(h < pq.peek() ){ //h가 힙의 루트 노트보다 작은 동안
            pq.poll(); // 루트 노트 삭제 
            h++;
            if(pq.size()==0) // 힙이 사이즈가 0일때, 런타임 에러 방지
                return h;
        }
        
        return h;
    }
}

 

문제에 다르면 n>=h이 된다. 따라서 최대가 되는 h를 구해야하는데, 최대힙을 떠올렸다. 

최대힙을 선언하여서 인용횟수를 넣어준다. 

h가 pq.peek()인 힙의 루트 노드보다 작을 때 while문을 실행한다. 따라서 인용횟수가 h번 이상인 논문이 h편 이상인 최대 수를 구할 수 있다. 

if문은 힙의 사이즈가 0이 되는 경우가 있어서 (테스트케이스9번) 추가해줬다. 

https://school.programmers.co.kr/questions/56783

프로그래머스

런타임에러가 자꾸 뜨길래 위의 글을 참고하여 수정하였다. 

 

 

 

3. 오늘의 회고

---

 

• 요즘 힙을 많이 사용해서 문제를 풀고 있다.