문제

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

명령어	설명
I 숫자	큐에 주어진 숫자를 삽입
D 1	큐에서 최댓값을 삭제
D -1	큐에서 최솟값을 삭제

---

입력

String 배열

["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]

---

출력

모든 연산을 처리한 후 큐가 비어있으면 {0,0} 비어있지 않으면 {최댓값, 최솟값}을 return

---

풀이

제한조건

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

접근방법

문제 제목에서 대놓고 이중우선순위큐라고 제시하였다.

힙을 이용해서 푸는것이 정석으로 보이지만, 연결리스트를 이용해서 풀었다.

우선 프로그래머스의 경우 시간제한과 메모리제한을 명확하게 제공하지 않아 알고리즘 선택이 어려운감이 있다.

일단 연산의 수가 최대 1,000,000개이다.

단순 연결리스트를 활용해서 O(NM)이나, 힙을 이용해서 O(NlogN)이나 이미 N이 1,000,000으로 크다.

효율성 체크가 없을것이라 판단하고 진행해보자.
연결리스트를 활용한다면 단순하다.
연결리스트를 오름차순으로 관리한다.

테스트케이스가 충분하지 않은 것인지 연결 리스트가 더 빠르게 나온다.

만약 힙을 사용한다면,
maxHeap과 minHeap을 두고 관리하는 방식을 사용한다.
(힙을 모른다면? : https://velog.io/@hyeokkr/HeapMaxMin)

• 연결리스트
  

• Heap 2개 사용
  

---

코드

• 연결리스트

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        List<Integer> list = new LinkedList();
        for(String s : operations){
            String[] split = s.split(" ");
            char operand = split[0].charAt(0);
            int num = Integer.parseInt(split[1]);
            if(operand == 'I'){
                if(list.isEmpty())
                    list.add(num);
                else{                    
                    int size = list.size();
                    if(size == 1){
                        if(list.get(0) > num)
                            list.add(0, num);
                        else
                            list.add(num);
                    }else{
                        boolean flag = false;
                        for(int i = 0 ; i < size; ++i){
                            if(num < list.get(i)){
                                list.add(i, num);
                                flag = true;
                                break;
                            }
                        }
                        
                        if(!flag)
                            list.add(num);
                    }
                }
            }else{
                if(!list.isEmpty()){
                    if(num == 1)
                        list.remove(list.size() - 1);
                    else
                        list.remove(0);
                }
            }
        }
        
        if(!list.isEmpty())
            return new int[] {list.get(list.size() - 1), list.get(0)};
        else
            return new int[] {0,0};
    }
}

• 힙

import java.util.*;
class Solution {
    public int[] solution(String[] operations) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        for (String op : operations) {
            String[] split = op.split(" ");
            char operation = split[0].charAt(0);
            int num = Integer.parseInt(split[1]);

            if (operation == 'I') {
                minHeap.offer(num);
                maxHeap.offer(num);
            } else if (!minHeap.isEmpty()) {
                if (num > 0) {
                    int max = maxHeap.poll();
                    minHeap.remove(max);
                } else {
                    int min = minHeap.poll();
                    maxHeap.remove(min);
                }
            }
        }

        if (minHeap.isEmpty()) {
            return new int[]{0, 0};
        } else {
            return new int[]{maxHeap.poll(), minHeap.poll()};
        }
    }
}