힙 - 우선순위큐 [JAVA]

문제

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

명령어수신 탑(높이)

I 숫자	큐에 주어진 숫자를 삽입합니다.
D 1	큐에서 최댓값을 삭제합니다.
D -1	큐에서 최솟값을 삭제합니다.

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

제한사항

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
• operations의 원소는 큐가 수행할 연산을 나타냅니다.
  • 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

나의 코드

import java.util.*;

public class DoublePriorityQueue {
	
	public static int[] solution(String[] operations) {
        int[] answer = new int[2];
       
        PriorityQueue<Integer> dpq = new PriorityQueue<>(Comparator.reverseOrder());
        String change = "";
        for(String s : operations) {
        	if(s.contains("I")) {
        		change = s.replace("I ", "");
        		dpq.offer(Integer.parseInt(change));
        	}else if(s.contains("D")) {
        		change = s.replace("D ", "");
        		if(change.equals("1")) {
        			dpq.poll();
        		}else if(change.equals("-1")) {
        			dpq = removelast(dpq);
        		}
        	}
        }
        System.out.println(dpq);
        if(dpq.size() > 1) {
        	answer[0] = dpq.poll();
        	answer[1] = lastIndex(dpq);
        }
        return answer;
    }
	
	
	public static PriorityQueue<Integer> removelast(PriorityQueue<Integer> dpq) {
	    PriorityQueue<Integer> pqnew = new PriorityQueue<Integer>(Comparator.reverseOrder());
	    while(dpq.size() > 1) {
	        pqnew.add(dpq.poll());
	    }
	    dpq.clear();
	    return pqnew;
	}
	
	public static int lastIndex(PriorityQueue<Integer> dpq) {
		while(dpq.size() > 1) {
			dpq.poll();
		}
		return dpq.poll();
	}
}

 

나의 풀이

우선 문제가 이중우선순위큐다. 이걸 문제 풀고 다시 생각해보니까 최소큐, 최대큐을 구현해서 하는게 맞는 것 같은데 다 풀고 알았으니..

기회가 된다면 이중우선순위큐를 구현해서 해결해보자.

1. 우선 solution method 제외 두 개의 method를 더 구현했다. 어떤 건지 알아보자.

2. 첫번째 removelast(PriorityQueue<Integer>) 인자로 PriorityQueue를 넘기면 while문을 통해 마지막 값을 삭제한 queue를 return

3. 두번째 lastIndex(PriorityQueue<Integer>) 인자로 받은 PriorityQueue의 마지막 Integer값을 return

4. 본격 soultion method 는 우선 answer array의 크기를 2로 할당한다.

5. String change 변수는 문제에서 주어진 입력되는 인자 값에서 명령 스트링을 제거한 값을 저장한다.

6. 만약 I가 들어가 있다면 "I " 를 공백으로 replace 시켜주고 남은 값을 Integer로 변환시켜 queue에 저장한다.

7. 만약 D가 들어가 있다면 "D "를 공백하로 replace 시켜준다.

8. 7에서 replace한 값이 "1"이라면 우선순위 큐에서 최댓값을 하나 제거한다. (큐를 생성할 때 Comparator.reverseOrder를 이용함)

9. 7에서 replace한 값이 "-1" 이라면 2에서 구현한 메서드(removelast)를 통해 최솟값을 하나 제거한다.

10. 여기서 for문이 끝나며 만약 우선순위큐의 사이즈가 1보다 크다면 answer[0]에는 최댓값을 넣는다.

11. answer[1] 에는 3에서 구현한 lastIndex를 통해 최솟값을 넣는다.

12. 그리고 return