[42628] 이중우선순위큐

✔ 이중우선순위큐

[프로그래머스 42628]

문제 분석하기

가장 작은 값과 가장 큰 값을 찾아야 하므로 두 개의 우선순위 큐를 사용하여 값을 저장하고, 삭제할 때 같이 삭제하도록 함

손으로 풀어보기

1. Min Heap과 Max Heap을 우선순위 큐로 구현
2. I일 경우 두 우선순위 큐에 값을 추가
3. D일 경우 두 우선순위 큐에서 최댓값/최솟값을 삭제
   • 빈 큐일 경우 해당 연산은 무시
   • 1일 경우 Max Heap에서 최댓값을 삭제 후 그 값을 Min Heap에서도 삭제
   • -1일 경우 Min Heap에서 최솟값을 삭제 후 그 값을 Max Heap에서도 삭제
4. 큐가 비어있다면 [0, 0] 반환, 비어있지 않다면 [Max Heap의 최댓값, Min Heap의 최솟값] 반환

슈도코드 작성하기

operations(이중 우선순위 큐가 할 연산)
minHeap(최솟값 우선순위 큐)
maxHeap(최댓값 우선순위 큐)
for(operations의 길이만큼) {
    if("I"일 경우) {
        minHeap, maxHeap에 숫자 저장
    }
    if("D"일 경우) {
        if(우선순위 큐가 비어 있다면) {
            해당 연산 무시
        }
        if(1일 경우) {
            maxHeap에서 최댓값 삭제 후 그 값을 minHeap에서도 삭제
        }
        if(-1일 경우) {
            minHeap에서 최솟값 삭제 후 그 값을 maxHeap에서도 삭제
        }
    }
}
answer = new int[2];
if(우선순위 큐가 비어 있지 않다면) {
    answer[0] = maxHeap의 최댓값
    answer[1] = minHeap의 최솟값
}
answer 반환

코드 구현하기

/**
 * 42628) 이중우선순위큐
 */
public class K003_42628 {
    // operations(이중 우선순위 큐가 할 연산)
    public int[] solution(String[] operations) {
        // minHeap(최솟값 우선순위 큐)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        // maxHeap(최댓값 우선순위 큐)
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (String operation : operations) {
            StringTokenizer st = new StringTokenizer(operation);
            String x = st.nextToken();
            int y = Integer.parseInt(st.nextToken());
            // "I"일 경우
            if (x.equals("I")) {
                // minHeap, maxHeap에 숫자 저장
                minHeap.add(y);
                maxHeap.add(y);
            }
            // "D"일 경우
            if (x.equals("D")) {
                // 우선순위 큐가 비어 있다면
                if (minHeap.isEmpty()) {
                    // 해당 연산 무시
                    continue;
                }
                // 1일 경우
                if (y == 1) {
                    // maxHeap에서 최댓값 삭제 후 그 값을 minHeap에서도 삭제
                    int max = maxHeap.poll();
                    minHeap.remove(max);
                }
                // -1일 경우
                if (y == -1) {
                    // minHeap에서 최솟값 삭제 후 그 값을 maxHeap에서도 삭제
                    int min = minHeap.poll();
                    maxHeap.remove(min);
                }
            }
        }
        int[] answer = new int[2];
        // 우선순위 큐가 비어 있지 않다면
        if (!minHeap.isEmpty()) {
            answer[0] = maxHeap.poll();
            answer[1] = minHeap.poll();
        }
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        K003_42628 solution = new K003_42628();

        String[] operations = { "I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1" };
        int[] result = solution.solution(operations);

        System.out.println(Arrays.toString(result));
    }
}