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

풀이 ①

1. 아이디어

1) x != 0 인 경우

• PriorityQueue에 x 추가
  => 최소 절댓값이 먼저 오도록 정렬

2) x == 0 인 경우

• PriorityQueue가 not empty
  => PriorityQueue에서 remove 및 출력
• PriorityQueue가 empty
  => 0 출력

2. 자료구조

• PriorityQueue<Integer>: 입력 정수 x 저장 및 정렬

3. 시간 복잡도

• PriorityQueue / Heap 의 시간 복잡도
  => 삽입 / 삭제: O(log n) (n: 노드 개수)
• 최대 총 n번 삽입 / 삭제 발생
  => 대충 최대 n log n
  => n 최대값 대입: 10^5 x log 10^5 = 5 x 10^5 << 1억 (1초)

코드

import java.io.*;
import java.util.PriorityQueue;

public class Main_PriorityQueue {
	static int n;		// 수행할 연산 개수
	static int x;		// 정수 x
	static PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> {
		int absDiff = Math.abs(o1) - Math.abs(o2);
		if (absDiff != 0)
			return absDiff;
		else
			return o1 - o2;
	});

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in)
		);
		StringBuilder sb = new StringBuilder();

		n = Integer.parseInt(br.readLine());

		for (int i = 0; i < n; i++) {
			x = Integer.parseInt(br.readLine());

			if (x != 0)
				pq.add(x);
			else {		// x == 0
				if (!pq.isEmpty())
					sb.append(pq.remove()).append("\n");
				else
					sb.append(0).append("\n");
			}
		}

		System.out.println(sb.toString());
	}
}

풀이 ②

1. 아이디어

• 절댓값 힙 직접 구현
  => 배열로 구현, add(), remove()
• 루트 노드에 최소 절댓값 위치

Abs Heap 구현

• 최소 절댓값 노드가 루트 노드 arr[1]에 위치
  (쉬운 구현을 위해 arr[0]은 사용 X)
• 부모, 자식 index 번호 관계
  => 왼쪽 자식의 index = 부모의 index 2
  => 오른쪽 자식의 index = (부모의 index 2) + 1
  => 부모의 index = 자식의 index / 2
  
  
  

1. void add(int item)
   1) 맨 뒤 arr[size+1]에 새로운 item 추가
   2) 새로운 노드 arr[size+1]을 부모 노드들과 비교해가면서 힙 정렬
   => ReHeapification Upward
   ① |부모| > |자식| 이면 교체
   ② |부모| == |자식| 이면, 더 작은 값이 부모가 됨
   
   
   
2. int remove()
   1) 루트 노드 arr[1]을 삭제
   2) 빈 루트 노드 arr[1]를 마지막 노드 arr[size]로 채움
   2) 루트 노드 arr[1] ~ arr[size-1] 까지 내려가면서 부모, 자식 비교해가면서 힙 정렬
   => ReHeapification Downward
   ① 왼쪽, 오른쪽 자식 노드 중, 절댓값이 더 작은 노드와 부모를 교체
   ② |왼쪽 자식| == |오른쪽 자식| 이면, 더 작은 값이 부모가 됨

2. 자료구조

• AbsHeap: 구현한 절댓값 힙

3. 시간 복잡도

• PriorityQueue / Heap 의 시간 복잡도
  => 삽입 / 삭제: O(log n) (n: 노드 개수)
• 최대 총 n번 삽입 / 삭제 발생
  => 대충 최대 n log n
  => n 최대값 대입: 10^5 x log 10^5 = 5 x 10^5 << 1억 (1초)

코드

import java.io.*;

class AbsHeap {
	private int[] arr;
	private int size;

	public AbsHeap(int length) {
		arr = new int[length];
	}

	public void add(int item) {
		arr[++size] = item;

		// Upward
		for (int i = size; i > 1; i /= 2) {
			int absParent = Math.abs(arr[i / 2]);
			int absChild = Math.abs(arr[i]);

			if (absParent > absChild)			// |부모| > |자식|
				swap(i / 2, i);
			else if (absParent == absChild) {	// |부모| == |자식|
				if (arr[i / 2] > arr[i])		// 부모 > 자식
					swap(i / 2, i);
			}
			else
				break;
		}
	}

	public int remove() {
		int root = arr[1];		// 기존 루트 노드 (최소 절댓값)
		arr[1] = arr[size--];	// 빈 루트 노드를 맨 뒤의 노드로 채움

		// Downward
		for (int i = 1; i * 2 <= size; ) {
			int absParent = Math.abs(arr[i]);
			int absLeftChild = Math.abs(arr[i * 2]);
			int absRightChild = Math.abs(arr[i * 2 + 1]);

			// |부모| < |자식| 또는
			// |부모| == |자식| && 부모 < 자식
			boolean isLeftSorted = (absParent < absLeftChild) ||
					(absParent == absLeftChild && arr[i] < arr[i * 2]);
			boolean isRightSorted = (absParent < absRightChild) ||
					(absParent == absRightChild && arr[i] < arr[i * 2 + 1]);

			if (isLeftSorted && isRightSorted)
				break;
			else if (absLeftChild < absRightChild) {	// 절댓값이 더 작은 자식과 부모 교체
				swap(i, i * 2);
				i = i * 2;
			}
			else if (absLeftChild > absRightChild) {	// 절댓값이 더 작은 자식과 부모 교체
				swap(i, i * 2 + 1);
				i = i * 2 + 1;
			}
			else {		// |왼쪽 자식| == |오른쪽 자식| => 값이 더 작은 자식과 부모 교체
				if (arr[i * 2] < arr[i * 2 + 1]) {
					swap(i, i * 2);
					i = i * 2;
				}
				else {
					swap(i, i * 2 + 1);
					i = i * 2 + 1;
				}
			}
		}

		return root;
	}

	public int size() { return size; }
	public boolean isEmpty() { return size == 0; }

	private void swap(int idx1, int idx2) {
		int temp = arr[idx1];
		arr[idx1] = arr[idx2];
		arr[idx2] = temp;
	}
}

public class Main_DevHeap {
	static int n;			// 수행할 연산 개수
	static int x;			// 입력 정수 x
	static AbsHeap absHeap;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in)
		);
		StringBuilder sb = new StringBuilder();
		
		n = Integer.parseInt(br.readLine());
		absHeap = new AbsHeap(n + 1);
		
		for (int i = 0; i < n; i++) {
			x = Integer.parseInt(br.readLine());
			
			if (x != 0)
				absHeap.add(x);
			else {		// x == 0
				if (!absHeap.isEmpty())
					sb.append(absHeap.remove()).append("\n");
				else
					sb.append(0).append("\n");
			}
		}
		
		System.out.println(sb.toString());
	}
}