[Algorithms] 백준 7662 이중 우선순위큐

개념

PriorityQueue : <Integer> 자료형을 사용했을때 오름차순으로 자동 정렬된다. 

 

 

아이디어

1.내림차순 큐, 오름차순 큐 두개 만들기

2. D -1 일때, D 1일때 각각 제거 

3. qMax 와 qMin에서 각각 중복 제거 해주기 

---

다른 아이디어

덱 사용하거나 트리맵을 사용해서 할 수 있을것 같다. 

 

문제점 

테케는 맞는데 틀렸습니다가 떠서 아직 해결 못했습니다.

package boj;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class boj7662_이중우선순위큐 {
	static class Pair {
	    int idx;
	    long value;
	 
	    Pair(int idx, long value) {
	        this.idx = idx;
	        this.value = value;
	    }
	}
	static class descend implements Comparator<Pair> {
	    @Override
	        public int compare(Pair p1, Pair p2) {
	        // TODO Auto-generated method stub
	        if (p1.value < p2.value) {
	            return 1;
	        } else {
	            return -1;
	        }
	    }
	}
	 
	static class ascend implements Comparator<Pair> {
	    @Override
	        public int compare(Pair p1, Pair p2) {
	        // TODO Auto-generated method stub
	        if (p1.value < p2.value) {
	            return -1;
	        } else {
	            return 1;
	        }
	    }
	}
	private static int T;
	private static int K;
	private static String charTmp;
	private static long num;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st ;
		T = Integer.parseInt(br.readLine());
		for (int i = 0; i < T; i++) {
			K = Integer.parseInt(br.readLine()); // q에 적용할 연산의 갯수 
			PriorityQueue<Pair> qMin = new PriorityQueue<>(new ascend());
			PriorityQueue<Pair> qMax = new PriorityQueue<>(new descend());
			boolean visited[] = new boolean[K];
			
			for(int j=0; j<K; j++) { //K개 연 
				st = new StringTokenizer(br.readLine(), " ");
				charTmp = st.nextToken(); //I,D
				num = Long.parseLong(st.nextToken()); //value
				
				
				if(charTmp.equals("I")) {
					Pair p = new Pair(j,num);
					qMin.add(p);
					qMax.add(p);
					//System.out.println(qMin.peek() + "왜 안됨?");
				}
				else {
					if(num ==1) { //최대값 삭제 
						if(!qMax.isEmpty()) {
							Pair p = qMax.peek();
							if(!visited[p.idx]) {
								qMax.poll();
								visited[p.idx]=true;
							}
						}
						
					}
					else { //최소값 삭제 
						if(!qMin.isEmpty()) {
							Pair p = qMax.peek();
							if(!visited[p.idx]) {
								qMin.poll();
								visited[p.idx]=true;
							}
						}

					}
				}// end case of charTmp =="D" 
				
				//중복 삭제 처리 
				while(!qMin.isEmpty()) {
	                if (!visited[qMin.peek().idx]) {
	                    break;
	                } else {
	                    qMin.poll();
	                }
	            }
	            while(!qMax.isEmpty()) {
	                if (!visited[qMax.peek().idx]) {
	                    break;
	                } else {
	                    qMax.poll();
	                }
	            }

			}//end k
			if(qMax.isEmpty() || qMin.isEmpty())
			System.out.println("EMPTY");
			else {
				System.out.println(qMax.peek().value + " "+ qMin.peek().value);
			}
			
		}///end tc

	}//end main
}//end class