이중우선순위큐

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

문제 설명

• 주어진 파라미터: String[] operations
• 반환값: int[]
  • 모든 연산 처리 후 값이 큐가 비면 [0,0]
  • 큐가 있으면 [최댓값, 최솟값]
• I 숫자 → 큐에 주어진 숫자를 삽입
• D 1 → 큐에서 최댓값을 삭제
• D -1 → 큐에서 최솟값을 삭제
• operations는 1 ≤ ≤ 1000000 이하 배열
• “명령어 데이터” 형식의 문자열
• 최댓값 최솟값이 둘 이상일 경우 하나만 삭제
• 빈 큐에 데이터 삭제 명령 시 연산 무시

풀이 방식

1. Queue를 돌면서 최댓값 최솟값을 찾으면 수행시간 문제? $10^6$이라 애매..
2. operations를 명령어 별로 구분할 방법이 필요하다.
3. 자료를 저장해 놓을 자료구조 → ArrayList?
4. operations는 크게보면 “I”, “D” 명령어 두개로 나뉜다 → D는 다시 그 뒤에 숫자가 1, -1인지 두개로 나뉜다
5. I일 경우에는 숫자를 넣어주기만 하면 된다. → 정렬 Arrays.sort 사용?

코드

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        
        // 1. 넣을 자료구조 선언 
        List<Integer> list = new ArrayList<>();
        
        // 2. opertions를 돌면서 명령어 확인 
        for(int i = 0; i < operations.length; i++){
            // 시작부터 정렬
            Collections.sort(list);
            
            if(operations[i].charAt(0) == 'I'){ // 삽입 명령어 
                operations[i] = operations[i].replace("I", "").replace(" ",""); // 숫자만 추출 
                //System.out.println("숫자 삽입");
                
                // 삽입 후 정렬 
                list.add(Integer.parseInt(operations[i]));
                
            }else if(operations[i].charAt(0) == 'D'){ // 삭제 명령어 
                // 만약 리스트가 비어져 있으면 통과 
                if(list.size() == 0) continue;
                
                operations[i] = operations[i].replace("D", "").replace(" ","");
                
                if(operations[i].equals("1")){ // 최댓값 삭제 명령어  
                    //System.out.println("최대값 삭제");
                    list.remove(list.size()-1);
                    
                }else{ // 최솟값 삭제 명령어 
                    //System.out.println("최솟값 삭제");
                    list.remove(0);
                }
            }
        }
        
        // 출력 
        if(list.size() == 0){
            return new int[]{0,0};
        }else{
		        Collections.sort(list); // 중요!! 
            return new int[]{list.get(list.size() -1), list.get(0)};
        }
        
    }
}

테스트 케이스 오류가 나는데 반례 → 마지막 정렬이 되지 않아 문제가 발생

회고

ArrayList로 풀 경우 Collections.sort()를 해야하는데 이 부분에서 O(N log N)이 소요돼 연산 횟수가 많아지면 문제가 될 수 있다.

삭제 시 첫번째 값을 삭제하면 인덱스를 당기는 부분에서 O(N)의 연산이 필요하다

⇒ 한번에 최솟값, 최댓값을 알아내기에는 매번 정렬을 사용해야하기 때문에 매우 비효율적이다.

⇒ PriorityQueue를 2개 사용해 하나는 내림차순, 하나는 오름차순으로 정렬해 삽입의 경우 둘다 삽입, 삭제의 경우 둘 중 하나를 골라 삭제한다면 정렬에서 생기는 문제를 해결할 수 있다.

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        
        // 두가지 큐 선언(내림차순, 올림차순)
        Queue<Integer> minpq = new PriorityQueue<>();
        Queue<Integer> maxpq = new PriorityQueue<>(Collections.reverseOrder());

        for (String operation : operations) {
            
            if (operation.startsWith("I ")) { // 삽입 명령어 
                int n = Integer.parseInt(operation.substring(2));
                
                // 두가지 큐에 모두 삽입 
                minpq.offer(n);
                maxpq.offer(n);
                
            } else if (!minpq.isEmpty() && operation.equals("D -1")) { // 삭제 명령어 
                maxpq.remove(minpq.poll());
                
            } else if (!maxpq.isEmpty() && operation.equals("D 1")) { // 삭제 명령어
                minpq.remove(maxpq.poll());
            }
        }

        if (minpq.isEmpty() && maxpq.isEmpty()) {
            return new int[]{0, 0};
        }

        return new int[]{maxpq.poll(), minpq.poll()};
    }
}

---

참 쉽쥬잉?