[백준] 단계별로 풀어보기(단계:22,우선순위 큐,JAVA)11286번, 절댓값 힙

문제 링크

11286번: 절댓값 힙

 

---

주의사항

• 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이 나옵니다.

 

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

문제에서는 절대값이 작은 값을 오름차순

절대값이 같을 경우 숫자가 더 작은 값을 오름차순으로 정렬하라고 설명하고 있습니다.

그에 맞게 우선순위 큐에 Comparator<>을 사용해서 조건을 만들어주시면 됩니다.

Comparator에서 return 값이 음수이면 오름차순 양수이면 내림차순입니다.

 

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

1. 우선순위 큐를 선언해줍니다.(우선순위 조건은 절대값에 따른 분류)

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

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

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

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

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• 우선순위 큐를 선언하였으며 절대값에 따라 달라지므로 Comparator을 사용하여 조건을 설정하였습니다.
• 입력 값이 '0'이외에 정수값이면 큐에 push(), '0'이면 poll()하도록 하였습니다.
• BufferedWriter에 입력값에 따른 명령어 실행 결과를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
    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
        //우선순위 큐 작성
    	PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
		@Override
        		//절대값에 따른 조건
			public int compare(Integer o1, Integer o2) {
            			//절대값이 같을 때
				if(Math.abs(o1) == Math.abs(o2)) {
					if(o1<o2)
						return -1;
					else
						return 1;
				}else //절대값이 다를 때
					return Math.abs(o1)-Math.abs(o2);
			}
		});
        //-------입력값 저장 및 명령어 결과 저장------
        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	//'0'이외에 정수일 때
        		queue.add(command);
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}