[백준 11286번] 절댓값 힙 (JAVA)

백준 11286번 문제  - 절댓값 힙

11286번: 절댓값 힙

---

문제 분석

 

 

• N개의 수를 입력
• 절댓값 힙: 배열에서 가장 작은 절대 값 출력 + 동일한 절대 값이 존재하면 음수의 값을 먼저 출력
  → 출력 후 배열에서 제거 
  ▶ 배열에서 절댓값 작은 수로 동일 값일 시 음수가 우선시 되게 배열 정렬 
• 입력 수가 0이면 절댓값 힙 출력
• 입력 수가 0이 아니면 절댓값 힙 배열에 추가

 

---

해결 키 포인트

• Queue 개념 이해가 필요
• Queue Class가 자바에 존재
• PriorityQueue(우선순위 큐) 개념 이해 필요
• PriorityQueue Class가 자바에 존재
• PriorityQueue의 우선순위 조건 변경 

---

 

큐(Queue) 설명

 

큐의 구조는 다음과 같다. 즉 큐의 특징은 "삽입과 삭제 연산 방식: FIFO(선입선출)" 이다

• FIFO: First-in First-out 

Do It! 알고리즘 코딩 테스트 기본

 큐는 너비 우선 탐색(BFS) 종류의 코딩 테스트에 효과적 

 

큐  용어

 

위치

• rear: 큐에 가장 끝 데이터
• front: 큐에서 가장 앞의 데이터

 

연산

• add: rear 위치에 새로운 데이터를 삽입
• poll: front 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
• peek: front 위치에 현재 있는 데이터를 단순 확인

---

우선순위 큐(Priority Queue) 설명

 

우선순위 큐는 일반적인 큐와 동일하게 FIFO 구조를 가진다.

하지만 추가적으로 우선순위라는 개념이 추가되어, 들어온 순서대로 나가는 것이 아닌 "우선순위가 높은 순서대로 나가는 구조"이다

 

PriorityQueue의 우선순위 조건 변경 방법

• PriorityQueue 클래스에서 public int compare(Object o1, Object o2) 를 재정의한다.
• PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> { ... }) 생성할 때 compare를 재정의한다. 

 

→ 둘 다 동일하게 PriorityQueue의 compare함수를 재정의하는 것이므로 편한 방법을 사용하여라

 

★ 재정의 할 때 o1에게 높은 우선순위를 주고 싶으면 -1, o2에게 높은 우선순위를 주고 싶으면 1 return ★

---

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String [] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// N 입력
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		
		// PriorityQueue 제작
		PriorityQueue<Integer> queue = new PriorityQueue<>((x, y) -> {
			// x, y의 비교 우선순위 설정
			// x에게 높은 우선순위를 주고 싶으면 음수값 return
			
			// 두개의 수 절대 값
			int absX = Math.abs(x);
			int absY = Math.abs(y);
			
			// 두 값이 같을 경우
			if(absX == absY) {
				// x가 y보다 작거나 같을 경우 : x가 음수 or x,y 같은 값
				if(x<=y) 
					return -1; // x에게 높은 우선순위를
				else 
					return 1; // y에게 높은 우선순위를
			}
			
			// x가 y보다 작은 절대값 수일 경우
			else if(absX < absY ) 
				return -1;  // x에게 높은 우선순위를
			
			// x가 y보다 큰 절대값 수일 경우
			else
				return 1; // y에게 높은 우선순위를
		});
		
		// 배열 입력 받으면서 동시에 Queue 작업 시작
		for(int i=0;i<N;i++) {
			// num 입력 받기
			st = new StringTokenizer(br.readLine());
			int num = Integer.parseInt(st.nextToken());
			
			// num == 0 : 절대값 가장 작은 수 꺼내기
			if(num == 0) {
				// queue가 비워있으면 0 출력
				if(queue.isEmpty())
					bw.write("0\n");
				// queue에 값이 존재하면 맨 위에 값 출력
				else
					bw.write(queue.poll()+"\n");
			}
			
			//  num != 0 : queue에 값 넣기
			else {
				queue.add(num);
			}
		}
		bw.flush();
		bw.close();
	}
}