프로그래머스(Programmers) : 이중 우선순위 큐

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

프로그래머스

이번엔 Programmers의 이중 우선순위 큐다.

풀고난 뒤 다른 사람의 풀이를 보니, 정말 우선순위 큐를 2개를 사용해 풀었던데, 2개의 큐를 사용해 문제를 풀고 2개의 큐에 모두 저장되어 있는 원소만 AND 조건을 사용해서 걸러낸다면 되는 것이었다.

 

나는 좀 다르게 풀었다.

아래의 코드를 확인해보면 알겠지만, 하나의 리스트를 두고 리스트를 삽입할 때 정렬을 한다는 조건을 두었다.

O(nlogn)인 Collection.sort()는 O(logn)인 Heap 정렬을 사용하는 PriorityQueue에 비할 방법은 아니다.

하지만 분명히 삽입에 대해서 O(1) 이상의 시간복잡도가 존재하는 만큼,

삽입에서의 이정도 시간 복잡도가 나오는 건 문제에서 용인될수 있다고 판단했다.

 

조금 어필을 해볼 수 있는 것은.. 공간을 적게 썼다 정도??

하지만 공간과 시간 중 포기해야하는 요소는 공간인 건 알고 있다... 시간은 다시 돌아오지 않으니까...

 

구해야할 것

리스트의 최댓값과 최솟값

 

 

1.원소를 저장할 리스트를 선언한다

(ArrayList,LinkedList 모두 상관 없으나 배열의 중간에 넣을 가능성을 염두해 LinkedList로 접근)

2.명령어에 따라 원소를 넣으면서 정렬 혹은 원소를 삭제한다.

3.해당 리스트의 첫번째 값과 끝 값에는 항상 최솟값과 최댓값이 있을 것이니 해당 값을 뽑아 정답으로 반환한다.

 

아래는 코드 전문이다.

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        List<Integer> list=new LinkedList<Integer>();
        
        for(String s: operations){
            String[] oper=s.split(" ");
            if(oper[0].equals("I")){
                list.add(Integer.parseInt(oper[1]));
                Collections.sort(list);
            } else if(oper[0].equals("D")){
                if(Integer.parseInt(oper[1])==1){
                    if(!list.isEmpty())
                        list.remove(list.size()-1);
                } else if(Integer.parseInt(oper[1])==-1){
                    if(!list.isEmpty())
                        list.remove(0);
                }
            }
        }
        int[] answer=new int[2];
        if(list.isEmpty()){
            answer[0]=0;
            answer[1]=0;
        } else{
            answer[0]=list.get(list.size()-1);
            answer[1]=list.get(0);
        }
        
        return answer;
    }
}