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

💡문제

[Silver II] 최소 힙 - 1927

문제 링크

성능 요약

메모리: 29732 KB, 시간: 1428 ms

---

🤔접근법

문제 요약

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

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

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

풀이법

⭕ 접근 방법. 우선순위큐

🔑 PriorityQueue를 사용하자!

위와 같이 PQ를 사용하여 작은 우선으로 빠져 나올 수 있도록 자료구조를 생성할 수 있다.

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

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

---

😎SUCCESS

고냥 단박에 성공

 

 

 

---

•  

👩‍💻 코드

import java.util.*;

import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException {		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		PriorityQueue<Integer> queue = new PriorityQueue<>();

		int N = Integer.parseInt(br.readLine());

		

		for(int i=0; i<N; i++) {

			int val = Integer.parseInt(br.readLine());

			

			if(val == 0) {

				if(queue.isEmpty())

					System.out.println("0");

				else

					System.out.println(queue.poll());

			}

			else

				queue.add(val);

		}

	}

}

99클럽 코딩테스트 준비 개발자 취업 항해99 TIL