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

문제

https://programmers.co.kr/learn/courses/30/lessons/42628

코딩테스트 연습 - 이중우선순위큐

 

접근법

단순하게 직관적으로 생각했다.

큐에 숫자가 삽입이 될때는 항상 정렬된 상태를 유지해야한다.

처음에는 우선순위큐를 사용했는데 힙에 삽입이 되듯이 정렬이 되어서 그냥 offer만 한 상태에서는 오름차순으로 정렬이 되지 않았다.

아직 우선순위 큐에 사용이 좀 미숙하다.

그래서 그냥 List를 정렬해가면서 풀었다.

삽입하고 삭제하는 연산이 많아서 LinkedList를 사용했다.

for문 안에 또 정렬을 하면 시간복잡도가 높게 나오지 않을까 걱정했는데 생각보다 짧게 걸렸다.

 

코드

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        List<Integer> pq = new LinkedList<>();

        for(String operation : operations){
            String[] str = operation.split(" ");

            if(str[0].equals("I")){
                pq.add(Integer.valueOf(str[1]));
                Collections.sort(pq);

            }else if(str[0].equals("D")){
                if(pq.isEmpty())
                    continue;

                if(str[1].equals("1")){
                    pq.remove(pq.size()-1);
                }else if(str[1].equals("-1")){
                    pq.remove(0);
                }
            }
        }

        if(pq.isEmpty()){
            return new int[] {0,0};
        }

        return new int[] {pq.get(pq.size()-1), pq.get(0)};
    }
}