[백준] 단계별로 풀어보기(단계:22,우선순위 큐,JAVA)11279번, 최대 힙

문제 링크

11279번: 최대 힙

 

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

우선순위 큐는 일반적인 큐와 조금의 차이점이 존재합니다.

우선순위 큐에 입력될 때마다 우선순위 조건에 따라서 순서가 바뀌어서 poll()값이 우선순위가 가장 높은 것을 나오게 되는 것입니다.

기본적인 우선순위 큐 설정은 숫자 오름차순으로 되어있습니다.

예를들어 우선순위 큐에 1 5 3 7 2를 push() 해보겠습니다.(우선순위는 숫자 오름차순)

1. 숫자 1 push

1

2. 숫자 5 push

1

5

3. 숫자 3 push

1

3

5

4. 숫자 7 push

1

3

5

7

5. 숫자 2 push

1

2

3

5

7

우선순위 큐의 peek() = 1, poll()을 진행하면 1이 나옵니다.

만약 우선순위 조건이 숫자 내림차순이면

7

5

3

2

1

peek() = 7, poll() = 7이 나옵니다.

 

문제에서는 최대 힙을 구하는 것에서 우선순위 큐를 사용하면 간단하게 구현할 수 있습니다.

문제에서는 큰 값이 먼저 poll()되기 때문에 우선순위 조건은 내림차순으로 하였습니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. 우선순위 큐를 선언해줍니다.(우선순위 조건은 숫자 내림차순)

2. 숫자가 자연수 값이 입력되면 그 값을 우선순위 큐에 push()해줍니다.

3. 숫자 '0'이 입력되면 우선순위 큐에서 poll()을 진행합니다.

4. 우선순위 큐가 비어있을 때 '0'이 입력되면 0이 출력하도록 합니다.

5. 위 과정을 입력값 횟수만큼 입력값대로 결과를 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• 우선순위 큐를 선언하였으며 내림차순 조건으로 Colections.reverseOrder() 설정해주었습니다.
• 입력 값이 자연수이면 큐에 push(), '0'이면 poll()하도록 하였습니다.
• BufferedWriter에 입력값에 따른 명령어 실행 결과를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	//우선순위 큐 선언
	static PriorityQueue<Integer> queue = new PriorityQueue<Integer>(Collections.reverseOrder());
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWrtier
        //-----입력값 저장 및 명령어 실행-----
        int size = Integer.parseInt(br.readLine());
        for(int i=0;i<size;i++) {
        	int command = Integer.parseInt(br.readLine());
        	if(command == 0) {	//입력 '0'인 경우 poll()
        		if(queue.size()==0)
        			bw.write("0\n");
        		else
        			bw.write(queue.poll() + "\n");
        	}else	//자연수일 경우 push()
        		queue.add(command);
        	
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}