[백준 7662] 이중 우선순위 큐 (JAVA)

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

7662번: 이중 우선순위 큐

 

이 문제는 일단적으로 많이 알려진 풀이인 TreeMap을 사용하면 진짜 간단히 풀 수 있는 문제이지만,

 

필자의 성향상 구현 문제을 비열하게 컬렉션 프레임 워크를 사용해 풀고 싶진않았다.

 

그래서 조금 어려운 풀이로 가보려 한다.

 

이 문제를 푸는 아이디어는 최대 힙 하나, 최소 힙 하나, 그리고 방문배열 하나로 푸는것이다.

 

문제 제목이 이중 우선순위 큐이니 최대힙,최소힙 두개의 힙을 사용한다는건 어느정도 느낌이 올것이다.

 

그런데 방문배열? 이런 생각이 들 수 있다.

 

최대힙, 최소힙만으로 문제를 풀려고 접근하면 데이터의 입출력에 따라 최대힙에서는 이미 사용처리가 되어

없는 데이터인데 최소힙에서는 아직 남아있는 상황이 발생할 수 있기 때문에

 

방문배열을 사용해야한다.

 

이 배열은 DB의 PK를 지정할때 sequence를 사용해 지정하는것과 같은 아이디어를 사용했다.

 

같은 데이터가 들어올수 있기 때문에 데이터만으로는 현재 데이터의 입출력을 관리할수 없다.

그렇기 때문에 각 데이터의 입력시마다 데이터에 기본키를 하나 부여하여 사용하는것이다.

그럼 같은 데이터일지라도 들어온 순서에 따라 다른 의미를 갖는 데이터가 되기 때문에 유일하게 식별할수 있다.

 

자세한 풀이는 코드로 작성하며 진행하겠다.

 

먼저 각 데이터에 유일키를 부여해서 저장할수 있도록 데이터를 의미하는 클래스를 하나 만들도록 하겠다.

 

class MyData { 
	
	// 시퀀스로 데이터마다 유일키를 갖도록 해서 같은 데이터를 구분한다.
	
	int id;
	Integer data;
	
	MyData(int id, Integer data){
		this.id = id;
		this.data = data;
	}
}

 

 

그리고 최대 힙, 최소 힙 두개의 힙을 구현해 사용해야 하므로 그냥 힙 클래스를 하나 만드는데

상속받아 일부만 수정해 다시 사용할수 있도록 추상클래스로 만들도록 하겠다.

 

힙의 구현에 대한 설명은 아래 링크를 참조하면 될것이다.

 

https://0bliviat3.tistory.com/37

[자료구조] 힙(heap) 의 구현 (JAVA) + 우선 순위 큐

 

abstract class Heap {
}

 

 

이 추상클래스는 힙을 구성해야하므로 

힙의 마지막노드를 의미하는 자원, 그리고 힙으로 사용할 배열을 하나 멤버 변수로 선언하겠다.

이때 배열은 이전에 선언한 데이터를 의미하는 클래스로 선언한다.

 

	private int node;
	
	private MyData[] heap;

 

 

그리고 현재 힙에대해 초기화 시켜줄 메소드도 하나 선언해준다.

 

	public void reset(int k) {
		node = 0;
		heap = new MyData[k + 1];
	}

 

 

힙이 비어있는지 확인할 메소드도 하나 선언한다.

루트노드가 null이라면 힙이 비어있단 의미이므로 true를 리턴 할 수 있도록 만들어준다.

 

	public boolean isEmpty() {
		if(heap[1] != null) return false;
		return true;
	}

 

 

다음으로는 최대힙과 최소힙의 차이라고 할수 있는 부등호에 대해 

재정의해 사용할수 있도록 추상메소드를 선언해준다.

첫번째 인자엔 부모노드 두번째 인자로는 자식노드를 받도록 설계했다.

 

	protected abstract boolean compare(MyData p, MyData c);
	protected abstract boolean compare2(MyData p, MyData c);

 

 

교환 메소드나 삽입메소드, 삭제메소드는 이전에 힙 구현시 다루었으므로 설명은 생략하도록 하겠다.

조금 다른점이 있다면 힙을 구성할때 조건문에서 사용하던 부등호 대신 앞서 선언한 추상 메소드를

사용하도록 바꿔주었다는 점이다.

 

	private void exchange(int a, int b) {
		MyData temp = heap[a];
		heap[a] = heap[b];
		heap[b] = temp;
	}
	
    	public void add(int id,int data) {
		heap[++node] = new MyData(id,data);
		for(int i = node; i > 1; i/=2) {
			if(compare(heap[i / 2],heap[i])) {
				exchange(i/2,i);
			}
		}
	}
    
    
    	public MyData getRoot() {
		if(node == 0) return null;
		MyData root = heap[1];
		heap[1] = heap[node];
		heap[node--] = null;
		int now = 1;
		while(now * 2 <= node) {
			int left = now * 2;
			int right = now * 2 + 1;
			if(compare(heap[now],heap[left]) || compare(heap[now],heap[right])) {
				if(compare2(heap[left],heap[right])) {
					exchange(now,left);
					now = left;
				}else {
					exchange(now,right);
					now = right;
				}
			}else {
				break;
			}
		}
		return root;
	}

 

힙 추상클래스 코드 전문 

abstract class Heap {
	
	private int node;
	
	private MyData[] heap;
	
	public void reset(int k) {
		node = 0;
		heap = new MyData[k + 1];
	}
	
	public boolean isEmpty() {
		if(heap[1] != null) return false;
		return true;
	}
	
	private void exchange(int a, int b) {
		MyData temp = heap[a];
		heap[a] = heap[b];
		heap[b] = temp;
	}
	
	protected abstract boolean compare(MyData p, MyData c);
	protected abstract boolean compare2(MyData p, MyData c);
	
	public void add(int id,int data) {
		heap[++node] = new MyData(id,data);
		for(int i = node; i > 1; i/=2) {
			if(compare(heap[i / 2],heap[i])) {
				exchange(i/2,i);
			}
		}
	}
	
	public MyData getRoot() {
		if(node == 0) return null;
		MyData root = heap[1];
		heap[1] = heap[node];
		heap[node--] = null;
		int now = 1;
		while(now * 2 <= node) {
			int left = now * 2;
			int right = now * 2 + 1;
			if(compare(heap[now],heap[left]) || compare(heap[now],heap[right])) {
				if(compare2(heap[left],heap[right])) {
					exchange(now,left);
					now = left;
				}else {
					exchange(now,right);
					now = right;
				}
			}else {
				break;
			}
		}
		return root;
	}
	
}

 

 

 

이제 최소힙부터 상속받아 만들어보겠다.

 

compare 메소드는 add메소드와 getRoot 메소드에서 부모노드와 자식노드를 비교할때 사용하고

compare2 메소드는 getRoot 메소드에서 자식노드끼리 비교할때 사용한다.

이때 의미없는 값인 null 값을 갖는 노드를 가져 올 경우 가장 큰값으로 취급해 리프노드로 보내버릴수 있도록 했다.

class MinHeap extends Heap{

	@Override
	protected boolean compare(MyData p, MyData c) {
		// null은 가장 큰값을 의미 리프노드로 보내야 한다.
		if(p == null) return true; // 부모 또는 왼쪽이 더 큰값인 경우
		if(c == null) return false; // 자식 또는 오른쪽이 더 큰값인 경우
		return p.data > c.data;
	}

	@Override
	protected boolean compare2(MyData p, MyData c) {
		if(p == null) return false; // 부모 또는 왼쪽이 더 큰값인 경우
		if(c == null) return true; // 자식 또는 오른쪽이 더 큰값인 경우
		return p.data < c.data;
	}


	
}

 

 

이번엔 최대힙이다.

메소드를 재정의해 원한는 부호로 바꿔주되

이때의 null 값은 역시 가장 의미없는 값으로 리프노드로 갈 수 있도록 가장 작은 값으로 취급한다.

 

class MaxHeap extends Heap{

	@Override
	protected boolean compare(MyData p, MyData c) {
		// null은 가장 작은 값을 의미 리프노드로 보낸다.
		if(p == null) return true; // 부모 또는 왼쪽이 가장 작은 값인 경우
		if(c == null) return false; // 자식 또는 오른쪽이 가장 작은 값인 경우
		return p.data < c.data;
	}

	@Override
	protected boolean compare2(MyData p, MyData c) {
		if(p == null) return false; // 부모 또는 왼쪽이 가장 작은 값인 경우
		if(c == null) return true; // 자식 또는 오른쪽이 가장 작은 값인 경우
		return p.data > c.data;
	}


	
}

 

 

이제 이중우선순위 큐를 구현해보도록 하겠다.

 

이 클래스의 멤버변수로는 

이전에 선언한 추상클래스인 힙을 상속받아 만든 최대힙, 최소힙을 다형성을 사용해

배열로 한번에 관리해줄수 있도록 선언해준다.

 

	private Heap[] heap = {new MaxHeap(), new MinHeap()};

 

 

그리고 방문배열의 기본키로 사용할 시퀀스를 의미하는 변수, 방문배열을 하나 선언해주겠다.

 

	private int sequence;
	private boolean[] idArr;

 

다음으로는 이중 우선순위 큐를 초기화 시켜줄 메소드를 하나 만들어준다.

 

	public void clear(int k) {
		sequence = 0;
		idArr = new boolean[k + 1];
		heap[0].reset(k + 1);
		heap[1].reset(k + 1);
	}

 

 

삽입 메소드는 현재 최대힙, 최소힙 모두 삽입될수 있도록 하고,

이때 시퀀스를 하나 증가시킨다.

 

만약 이중우선순위 큐가 아닌 다중 우선순위 큐라면 배열로 힙을 관리하므로 반복문을 사용해 삽입하면 될것이다.

 

	public void add(int data) {
		heap[0].add(sequence, data);
		heap[1].add(sequence, data);
		sequence++;
	}

 

 

이제 삭제 메소드는 인자로 최대힙인지 최소힙인지 구분할 데이터를 받도록해서

해당하는 힙의 데이터를 삭제하도록 한다.

 

이때 방문배열에서 이미 방문처리가 되어있다는것은 다른 힙에서 이미 삭제처리가 되었단 의미이므로

반복문을 통해 방문처리가 되어있지 않은 데이터를 찾을때까지 연달아 삭제할수 있도록 한다.

 

	public Integer pop(int idx) { // 0 이면 max pop , 1이면 min pop
		if(!heap[idx].isEmpty()) {
			MyData data = heap[idx].getRoot();
			while(!heap[idx].isEmpty() && idArr[data.id]) {
				data = heap[idx].getRoot();
			}
			if(!idArr[data.id]) { // 삭제되지 않은 데이터의 경우 방문처리
				idArr[data.id] = true;
				return data.data;
			}
			
		}
		return null;
	}

 

 

 

이중 우선순위 큐 클래스 전문

class DualHeap {
	
	private Heap[] heap = {new MaxHeap(), new MinHeap()};
	
	private int sequence;
	private boolean[] idArr;
	
	public void clear(int k) {
		sequence = 0;
		idArr = new boolean[k + 1];
		heap[0].reset(k + 1);
		heap[1].reset(k + 1);
	}
	
	public void add(int data) {
		heap[0].add(sequence, data);
		heap[1].add(sequence, data);
		sequence++;
	}
	
	public Integer pop(int idx) { // 0 이면 max pop , 1이면 min pop
		if(!heap[idx].isEmpty()) {
			MyData data = heap[idx].getRoot();
			while(!heap[idx].isEmpty() && idArr[data.id]) {
				data = heap[idx].getRoot();
			}
			if(!idArr[data.id]) { // 삭제되지 않은 데이터의 경우 방문처리
				idArr[data.id] = true;
				return data.data;
			}
			
		}
		return null;
	}
	
	
}

 

 

이제 남은것은 main에서 입력형식과 출력형식만 맞춰주는 것이다.

해당 코드는 코드전문에 넣을 것이니 생략하도록 하겠다.

 

이제 작성된 코드로 예제를 실행시켜보면,

 

 

 

정확한 답을 내는것을 확인할수 있다

 

코드전문

 

package boj4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Boj7662_3 {
	
	/*
	 * 제출 完
	 */
	
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		DualHeap heap = new DualHeap();
		
		int t = Integer.parseInt(in.readLine());
		String[] order;
		while(t-- > 0) {
			int k = Integer.parseInt(in.readLine());
			heap.clear(k);
			
			while(k-- > 0) {
				order = in.readLine().split(" ");
				int num = Integer.parseInt(order[1]);
				if(order[0].equals("I")) {
					heap.add(num);
				}else {
					if(num > 0) {
						heap.pop(0);
					}else {
						heap.pop(1);
					}
				}
			}
			
			Integer num1 = heap.pop(0);
			Integer num2 = null;
			if(num1 != null) {
				heap.add(num1);
				num2 = heap.pop(1);				
			}
			if(num1 == null || num2 == null) {
				sb.append("EMPTY");
			}else {
				sb.append(num1).append(' ').append(num2);
			}
			sb.append('\n');
		}
		
		in.close();
		
		System.out.print(sb);
	}

}

class MyData { 
	
	// 시퀀스로 데이터마다 유일키를 갖도록 해서 같은 데이터를 구분한다.
	
	int id;
	Integer data;
	
	MyData(int id, Integer data){
		this.id = id;
		this.data = data;
	}
}

abstract class Heap {
	
	private int node;
	
	private MyData[] heap;
	
	public void reset(int k) {
		node = 0;
		heap = new MyData[k + 1];
	}
	
	public boolean isEmpty() {
		if(heap[1] != null) return false;
		return true;
	}
	
	private void exchange(int a, int b) {
		MyData temp = heap[a];
		heap[a] = heap[b];
		heap[b] = temp;
	}
	
	protected abstract boolean compare(MyData p, MyData c);
	protected abstract boolean compare2(MyData p, MyData c);
	
	public void add(int id,int data) {
		heap[++node] = new MyData(id,data);
		for(int i = node; i > 1; i/=2) {
			if(compare(heap[i / 2],heap[i])) {
				exchange(i/2,i);
			}
		}
	}
	
	public MyData getRoot() {
		if(node == 0) return null;
		MyData root = heap[1];
		heap[1] = heap[node];
		heap[node--] = null;
		int now = 1;
		while(now * 2 <= node) {
			int left = now * 2;
			int right = now * 2 + 1;
			if(compare(heap[now],heap[left]) || compare(heap[now],heap[right])) {
				if(compare2(heap[left],heap[right])) {
					exchange(now,left);
					now = left;
				}else {
					exchange(now,right);
					now = right;
				}
			}else {
				break;
			}
		}
		return root;
	}
	
}

class MinHeap extends Heap{

	@Override
	protected boolean compare(MyData p, MyData c) {
		// null은 가장 큰값을 의미 리프노드로 보내야 한다.
		if(p == null) return true; // 부모 또는 왼쪽이 더 큰값인 경우
		if(c == null) return false; // 자식 또는 오른쪽이 더 큰값인 경우
		return p.data > c.data;
	}

	@Override
	protected boolean compare2(MyData p, MyData c) {
		if(p == null) return false; // 부모 또는 왼쪽이 더 큰값인 경우
		if(c == null) return true; // 자식 또는 오른쪽이 더 큰값인 경우
		return p.data < c.data;
	}


	
}

class MaxHeap extends Heap{

	@Override
	protected boolean compare(MyData p, MyData c) {
		// null은 가장 작은 값을 의미 리프노드로 보낸다.
		if(p == null) return true; // 부모 또는 왼쪽이 가장 작은 값인 경우
		if(c == null) return false; // 자식 또는 오른쪽이 가장 작은 값인 경우
		return p.data < c.data;
	}

	@Override
	protected boolean compare2(MyData p, MyData c) {
		if(p == null) return false; // 부모 또는 왼쪽이 가장 작은 값인 경우
		if(c == null) return true; // 자식 또는 오른쪽이 가장 작은 값인 경우
		return p.data > c.data;
	}


	
}


class DualHeap {
	
	private Heap[] heap = {new MaxHeap(), new MinHeap()};
	
	private int sequence;
	private boolean[] idArr;
	
	public void clear(int k) {
		sequence = 0;
		idArr = new boolean[k + 1];
		heap[0].reset(k + 1);
		heap[1].reset(k + 1);
	}
	
	public void add(int data) {
		heap[0].add(sequence, data);
		heap[1].add(sequence, data);
		sequence++;
	}
	
	public Integer pop(int idx) { // 0 이면 max pop , 1이면 min pop
		if(!heap[idx].isEmpty()) {
			MyData data = heap[idx].getRoot();
			while(!heap[idx].isEmpty() && idArr[data.id]) {
				data = heap[idx].getRoot();
			}
			if(!idArr[data.id]) { // 삭제되지 않은 데이터의 경우 방문처리
				idArr[data.id] = true;
				return data.data;
			}
			
		}
		return null;
	}
	
	
}

 

 

진짜 오랜만에 상속과 다형성을 사용해 구현할수 있었던 문제였던거 같다.

이 문제를 풀면서 많은 공부가 되었다.