[Java] 백준(Baekjoon) 11279. 최대 힙

 

https://www.acmicpc.net/problem/11279

11279번: 최대 힙

 

 

 

---

 

풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
	static List<Integer> list= new ArrayList<>();
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub

		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		
		int cnt= Integer.parseInt(br.readLine());
		
		StringBuilder sb= new StringBuilder();
		
		for(int i=0;i<cnt;i++) {
			int num= Integer.parseInt(br.readLine());
			
			if(num==0) {
				if(list.isEmpty()) {
					sb.append("0\n");
				}else {
					sb.append(list.get(list.size()-1)+"\n");
					list.remove(list.size()-1);
					
				}
			}else {
				int idx= 0;
				if(!list.isEmpty()) {
					idx= Math.abs(Collections.binarySearch(list, num)+1);
				}
				list.add(idx, num);
				
			}
		}
		
		System.out.println(sb.toString());
	}
}

 

"최소 힙" 문제에서, 꺼내는 수를 리스트의 맨 뒤 index= (list.size()-1)로 변경(max 값)

 

---

 

최대 힙(Max-Heap)

=> 우선순위 큐(Priority Queue)를 활용하면 더 쉽게 구현할 수 있다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> que = new PriorityQueue<>(Collections.reverseOrder());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());

            if (num == 0)
                sb.append(que.size() == 0 ? 0 : que.poll()).append('\n');
            else que.add(num);
        }
        System.out.println(sb.toString());
    }
}