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

문제 링크

1927번: 최소 힙

---

주의사항

• 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를 사용하여 입력 값을 받았습니다.
• 우선순위 큐를 선언하였으며 오름차순은 기본 조건으로 default 조건으로 설정하였습니다.
• 입력 값이 자연수이면 큐에 push(),'0'이면 poll()하도록 하였습니다.
• BufferedWriter에 입력값에 따른 명령어 실행 결과를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

결과 코드

import java.io.*;
public class Main{
	//우선순위 큐(default 조건 오름차순)
    static PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
    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));
        //출력값 출력하는 BufferedWriter
        //-------입력값 저장 및 명령어 실행--------
        int N = Integer.parseInt(br.readLine());
        for(int i=0;i<N;i++) {
        	int command = Integer.parseInt(br.readLine());
        	if(command==0) {	//입력값 '0'일 때
        		if(queue.size()==0)	//큐에 아무것도 없을 때
        			bw.write("0\n");
        		else	//큐에 값이 존재할 때
        			bw.write(queue.poll() + "\n");
        	}else	//입력값이 자연수일 경우
        		queue.add(command);
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}