이중우선순위큐


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

문제보기
Alt text

소스코드

1. List를 활용한 방법

import java.util.*;

class Solution {
    public static int[] solution(String[] operations) {

        List<Integer> list = new LinkedList<>();
        int operationsLength = operations.length;

        for (int i = 0; i < operationsLength; i++) {
            String[] operation = operations[i].split(" ");

            if ("I".equals(operation[0])) { // 숫자 삽입
                list.add(Integer.parseInt(operation[1]));
                Collections.sort(list);
            } else if (list.size() != 0) {
                if ("1".equals(operation[1])) { // 최댓값 삭제
                    list.remove(list.size() - 1);
                } else { // 최솟값 삭제
                    list.remove(0);
                }
            }
        }

        if (list.size() != 0) {
            return new int[]{list.get(list.size() - 1), list.get(0)};
        } else {
            return new int[]{0, 0};
        }
    }
}

2. Queue를 이용한 방법

import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;

class Solution {
     public static int[] solution(String[] operations) {

        Queue<Integer> queueAsc = new PriorityQueue<>();
        Queue<Integer> queueDesc = new PriorityQueue<>(Collections.reverseOrder());
        int operationsLength = operations.length;

        for (int i = 0; i < operationsLength; i++) {
            String[] operation = operations[i].split(" ");

            if ("I".equals(operation[0])) { // 숫자 삽입
                int num = Integer.parseInt(operation[1]);
                queueAsc.add(num);
                queueDesc.add(num);
            } else {
                if ("1".equals(operation[1])) { // 최댓값 삭제
                    queueAsc.remove(queueDesc.poll());
                } else { // 최솟값 삭제
                    queueDesc.remove(queueAsc.poll());
                }
            }
        }

        Integer max = queueDesc.poll();
        Integer min = queueAsc.poll();

        if (max == null || min == null) {
            return new int[]{0, 0};
        } else return new int[]{max, min};
    }
}