[프로그래머스 42628번] 이중우선순위 큐

문제

번호

프로그래머스 42628번(링크)

내용

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

명령어	수신 탑(높이)
I 숫자	큐에 주어진 숫자를 삽입합니다.
D 1	큐에서 최댓값을 삭제합니다.
D -1	큐에서 최솟값을 삭제합니다.

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

제한사항

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

입출력 예

operations	return
[I 16,D 1]	[0,0]
[I 7,I 5,I -5,D -1]	[7,5]

입출력 예 설명

16을 삽입 후 최댓값을 삭제합니다. 비어있으므로 [0,0]을 반환합니다.
7,5,-5를 삽입 후 최솟값을 삭제합니다. 최대값 7, 최소값 5를 반환합니다.

언어

JAVA

 

---

풀이

이번 문제는 비교적 쉬운 문제였다.

입력으로 들어온 operations을 순차적으로 처리만 하면 되는 문제이다.

그 외에는 크게 다룰 내용이 없기에... 바로 코드 설명으로 들어가겠다.

 

코드 설명

우선, for 반복문을 이용하여 입력으로 들어온 operation을 파악해야한다.

 

숫자 삽입인 <pre>I 숫자</pre> 중 숫자는 정해져있는 상수가 아닌 변수에 해당하므로 맨 첫글자가 I인지 파악한다.

<pre>I 숫자</pre> 외에는 <pre>D 1</pre> 혹은 <pre>D -1</pre> 인데 이들은 모두 뒤에 추가적으로 변수가 붙는 것이 아닌, 고정되어 있는 것들이므로 String의 <pre>equal()</pre> 메소드를 이용하여 분별한다. 단, 큐가 비어있는 상태이면 무시하는 것이 조건이므로, <pre>queue.size()</pre>을 조건에 추가한다.

 

그런데 <pre>D 1</pre>의 경우는 조금 특이하다.

지금 사용 중인 큐는 min heap이기 때문에 최솟값을 파악하는 것은 <pre>peek()</pre>을 사용하면 되므로 간단하지만, 최댓값의 경우는 메소드를 지원하지 않기 때문이다.

따라서 우선순위 큐를 array로 변환하고, 정렬하는 과정이 필요된다.

현재 사용하는 우선순위 큐는 peek/remove을 할 때 최솟값만 뽑아내고, 그 외에는 정렬을 시행하지 않는다. 따라서 정렬하는 과정이 꼭 필요하다.

 

반복문이 끝나면 <pre>answer</pre>을 수정하면 된다.

만약 큐가 비어있다면 [0,0]을 출력하고 그렇지 않다면 [최댓값, 최솟값]을 출력하면 된다.

최댓값의 경우 위에서와 같은 이유로 array로 변환한 후 정렬하는 과정을 거쳐야 한다.

최솟값의 경우도 어차피 array를 이용해야 한다면 <pre>array[0]</pre>을 이용하는 것이 런타임을 줄일 수 있기 때문에 이를 이용하였다.(<pre>queue.peek()</pre>을 하게되면 최솟값을 찾는 시간이 낭비되기 때문)

 

---

코드

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = {};
        Queue<Integer> queue = new PriorityQueue<>();

        for (String i : operations) {
            if (i.charAt(0) == 'I') {
                queue.add(Integer.parseInt(i.substring(1).trim()));
            }
            else if (queue.size() > 0 && i.equals("D 1")) {
                Object[] arr = queue.toArray();
                Arrays.sort(arr);
                int max = (int) arr[arr.length - 1];
                queue.remove(max);
            }
            else if (queue.size() > 0 && i.equals("D -1")) {
                queue.remove();
            }
        }

        if(queue.size() == 0) {
            answer = new int[]{0, 0};
        }
        else {
            Object[] arr = queue.toArray();
            Arrays.sort(arr);
            int max = (int) arr[arr.length - 1];
            int min = (int) arr[0];
            answer = new int[]{max, min};
        }

        return answer;
    }
}