99클럽 코테 스터디 10일차 TIL /[백준]최대힙

 

💡문제

[Silver II] 최대 힙 - 11279

문제 링크

성능 요약

메모리: 38356 KB, 시간: 1604 ms

 

---

🤔접근법

문제 요약

• 주어진 자연수 x를 배열에 넣고, 0이 주어지면 가장 배열에서 가장 큰 값을 출력하는 문제

범위 체크 및 시간복잡도 예상

• 1 ≤ N ≤ 100,000 (N은 x가 주어지는 횟수)
• $O(N^2)$ 보다는 작아야한다.

풀이법

⭕ 접근 방법. 우선순위 큐

🔑 PriorityQueue를 사용하자!

static PriorityQueue<Integer> *pq* = new PriorityQueue<>((o1, o2) -> {return o2-o1;});

위와 같이 PQ를 사용하여 우선순위 조건을 변경하면 큰 값이 우선이 되도록 qp를 생성할 수 있다.

pq 는 힙으로 구성되어 있기 때문에 시간복잡도는 O(logN)을 가진다.

➡️ 해당 풀이법의 시간 복잡도 : $O(NlogN)$

 

---

 

😎SUCCESS

고냥 단박에 성공

 

---

👩‍💻 코드

package gugu;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Main10 {
    static int N;
    static PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> {
        return o2-o1;
    });
    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int x ;
        for (int i = 0; i < N; i++) {
            x = Integer.parseInt(br.readLine());
            if(x == 0){
                if(pq.isEmpty()){
                    System.out.println(0);
                }else{
                    System.out.println(pq.poll());
                }
                continue;
            }
            pq.add(x);
        }
    }
}