프로그래머스 3단계 - 이중우선순위큐(Python, Java)

깃허브:

https://github.com/MSIQOC/Programmers/blob/main/%EC%9D%B4%EC%A4%91%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84%ED%81%90.java

https://github.com/MSIQOC/Programmers/blob/main/%EC%9D%B4%EC%A4%91%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84%ED%81%90.py

 

 

https://programmers.co.kr/learn/courses/30/lessons/42628?language=java 

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

 

---

자바풀이

• 우선순위 큐를 하나는 오름차순으로 만들고 다른 하나는 내림차순으로 만들어줬다.
• qsize를 통해서 실제 큐의 길이를 알 수 있도록 해줬다.
• qsize가 0이면 큐가 빈걸로 간주했다.

주의해야할 반례

테스트 4를 보면 10과 20이 min큐와 max큐에 추가된 상황에서 max큐의 숫자를 지우게 되는데, min큐에는 여전히 20이 남아있는 상태로 계속 20보다 높은 숫자를 큐에 추가하게 돼서 문제가 일어난다.

이를 해결하기 위해서 qsize가 1인데 max큐와 min큐의 길이가 맞지 않는 경우 다 비워주고 있어야할 값 하나만 각각에 추가해주는 식으로 구현했다. 백준의 7662와 똑같은 문제인데 똑같은 알고리즘으로 백준에 제출하면 오답으로 나와서 백준 문제를 더 자세히 보거나 좀 더 고민을 해봐야할 것 같다.

//
//  Created by MinSeo on 2021/07/30.
//  Copyright ⓒ 2021 MinSeo Shin. All rights reserved.
//
import java.util.*;
import java.io.*;
class Solution {
    public int[] solution(String[] operations) {
        int[] answer = new int[2];
        PriorityQueue<Integer> qsmall = new PriorityQueue<>();
        PriorityQueue<Integer> qbig = new PriorityQueue<>(Collections.reverseOrder());
        int qsize = 0;
        for(String s : operations){
            StringTokenizer st = new StringTokenizer(s);
            String s1 = st.nextToken();
            int in = Integer.parseInt(st.nextToken());
            if(s1.equals("I")){
                qsmall.add(in);
                qbig.add(in);
                ++qsize;
            }
            else if(s1.equals("D")){
                if(qsize==0){}
                else if(in==1){
                    qbig.poll();
                    --qsize;
                }
                else if(in == -1){
                    qsmall.poll();
                    --qsize;
                }
                if(qsize==1 && (qbig.size()!=1 || qsmall.size()!=1)){
                    int a = qbig.peek();
                    while(!qbig.isEmpty())
                        qbig.poll();
                    while(!qsmall.isEmpty())
                        qsmall.poll();
                    qbig.add(a);
                    qsmall.add(a);
                }
                
            }
        }
        if(qsize!=0){
            answer[0] = qbig.peek();
            answer[1] = qsmall.peek();
        }
        return answer;
    }
}

---

파이썬 풀이

"""
Created by MinSeo on 2021/07/30.
Copyright ⓒ 2021 MinSeo Shin. All rights reserved.
 
"""
import heapq
def solution(operations):
    answer = []
    q = []
    for s in operations:
        s1, num = map(str, s.split())
        num = int(num)
        if s1 == "I" :
            q.append(num)
        elif s1 == "D" :
            if len(q) == 0:
                continue
            elif num == 1 :
                heapq._heapify_max(q)
                heapq._heappop_max(q)
            elif num == -1 :
                heapq.heapify(q)
                heapq.heappop(q)
    if len(q) == 0:
        answer.append(0)
        answer.append(0)
    else:
        heapq._heapify_max(q)
        answer.append(q[0])
        heapq.heapify(q)
        answer.append(q[0])
    return answer

미리 우선순위 큐를 정의해야하는 자바와 다르게 배열 하나로 최소 heapify와 최대 heapify가 다가능했기 때문에 구현이 훨씬 편리했다. 자바에서는 큐의 길이를 미리 알아야하기 때문에 qsize 변수가 필요했지만 파이썬에서는 len(q)로 모든게 다 해결이 됐다.