[프로그래머스 / Java] 코딩테스트 연습: 이중우선순위큐 (힙)

난이도: Level 3

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

프로그래머스

---

 

체감상 레벨3 문제치고는 쉬운 문제였다.

이정도면 솔직히 레벨2 중에서도 쉬운 문제가 아닐까 싶다.

 

큐를 정렬하려면 우선순위 큐를 사용해야 하는데, 이중우선순위큐는 자바 라이브러리에 존재하지 않는다.

그러므로 이것을 우리가 만들어야 한다는 것이다.

일단 우선순위 큐를 다음과 같이 내림차순 정렬한다.

참고로 여기에서는 Integer.compare(b, a) 대신 b - a로 작성해도 된다.

 

    // 내림차순 정렬한 우선순위 큐 => 맨 앞은 최댓값, 맨 뒤는 최솟값

    Queue<Integer> pq = new PriorityQueue<>((a, b) -> Integer.compare(b, a));

 

 

문제에 주어진 operations 배열을 반복문 돌려서 연산을 하나씩 수행하도록 만든다.

연산 코드가 I라면 그냥 우선순위 큐에 값만 삽입하면 된다.

값을 제거하기 전에는 큐가 비어있지 않은지 체크를 무조건 해야 한다.

연산 코드가 D이고, 숫자가 1이라면 그냥 우선순위 큐에서 값을 뽑으면 저절로 최댓값이 제거된다.

문제는 연산 코드가 D이고, 숫자가 -1인 경우(최솟값을 제거해야 하는 경우)이다.

여기서 이중우선순위큐를 구현해야 한다.

이중우선순위큐라고 해서 어려울 것 없다.

그저 임시 큐 하나를 만들어 놓고, 우선순위 큐에 남아있는 값들 중 1개만 빼고 나머지를 모두 뽑아서 임시 큐에 삽입한 다음, 우선순위 큐에 가장 마지막에 남아있던 값 하나를 뽑으면 최솟값이 제거된다.

그리고 임시 큐에 삽입했던 나머지 값들을 다시 우선순위 큐에 차례로 삽입하면 된다.

 

    for (String operation : operations) {

        String[] line = operation.split(" ");

        String op = line[0];    // 연산 코드

        int n = Integer.parseInt(line[1]);  // 숫자

       

        if (op.equals("I")) {       // 연산 코드가 I일 때

            pq.add(n);  // 큐에 주어진 숫자 삽입

        } else if (!pq.isEmpty()) { // 연산 코드가 D이고, 우선순위 큐가 비어있지 않을 때

            if (n == 1) {   // 숫자가 1일 때

                pq.poll();  // 우선순위 큐에서 가장 먼저 뽑은 숫자(최댓값) 삭제

            } else {        // 숫자가 -1일 때

                Queue<Integer> queue = new LinkedList<>();  // 임시 큐

               

                // 우선순위 큐에 남아있는 숫자가 1개가 될 때까지

                // 우선순위 큐에 있는 값들을 뽑아서 모두 임시 큐에 삽입

                while (pq.size() > 1) {

                    queue.add(pq.poll());

                }

               

                pq.poll();  // 우선순위 큐에서 가장 마지막에 뽑은 숫자(최솟값) 삭제

               

                // 임시 큐가 빌 때까지

                while (!queue.isEmpty()) {

                    // 임시 큐에 있던 값들을 뽑아서 모두 우선순위 큐에 삽입

                    pq.add(queue.poll());

                }

            }

        }

    }

 

 

가장 마지막으로 최댓값과 최솟값을 답 배열에 세팅하고 리턴하면 된다.

여기서 주의할 점은, 우선순위 큐에 값이 1개만 남아있을 때이다.

이때는 최댓값만 설정하고 리턴해버리면 오답이 되어버린다.

이것 때문에 도대체 이게 왜 틀렸나 싶었다.

우선순위 큐에 값이 1개만 남아있을 때에는 최댓값과 최솟값 모두 같은 값으로 설정해야 한다.

우선순위 큐에 값이 2개 이상 남아있을 때에는 가장 먼저 뽑은 값을 최댓값으로 설정하고,

우선순위 큐에 남아있는 숫자가 1개가 될 때까지 뽑은 다음, 마지막 1개를 뽑아서 최솟값으로 설정하면 된다.

우선순위 큐에 값이 아예 남아있지 않은 경우는 자동으로 {0, 0}이 리턴되므로 아무런 설정도 하지 않아도 된다.

왜나하면 내가 답 배열을 처음에 int[] answer = new int[2]; 로 초기화했기 때문에 모두 초기값이 0으로 설정됐기 때문이다.

 

    if (pq.size() == 1) {   // 우선순위 큐에 남아있는 숫자가 1개라면

        answer[0] = answer[1] = pq.poll();  // 남아있는 숫자 1개는 최댓값이자 최솟값

    } else if (pq.size() > 1) { // 우선순위 큐에 남아있는 숫자가 2개 이상이라면

        answer[0] = pq.poll();  // 우선순위 큐에서 가장 먼저 뽑은 숫자: 최댓값

       

        // 우선순위 큐에 남아있는 숫자가 1개가 될 때까지 우선순위 큐에 있는 값들을 뽑기

        while (pq.size() > 1) {

            pq.poll();

        }

       

        answer[1] = pq.poll();  // 우선순위 큐에서 가장 마지막에 뽑은 숫자: 최솟값

    }

   

    return answer;  // {최댓값, 최솟값} 배열 리턴

 

 

 

전체 코드

import java.util.*;
 
class Solution {
    public int[] solution(String[] operations) {
        int[] answer = new int[2];  // {최댓값, 최솟값} 배열
        // 내림차순 정렬한 우선순위 큐 => 맨 앞은 최댓값, 맨 뒤는 최솟값
        Queue<Integer> pq = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
        
        for (String operation : operations) {
            String[] line = operation.split(" ");
            String op = line[0];    // 연산 코드
            int n = Integer.parseInt(line[1]);  // 숫자
            
            if (op.equals("I")) {       // 연산 코드가 I일 때
                pq.add(n);  // 큐에 주어진 숫자 삽입
            } else if (!pq.isEmpty()) { // 연산 코드가 D이고, 우선순위 큐가 비어있지 않을 때
                if (n == 1) {   // 숫자가 1일 때
                    pq.poll();  // 우선순위 큐에서 가장 먼저 뽑은 숫자(최댓값) 삭제
                } else {        // 숫자가 -1일 때
                    Queue<Integer> queue = new LinkedList<>();  // 임시 큐
                    
                    // 우선순위 큐에 남아있는 숫자가 1개가 될 때까지 
                    // 우선순위 큐에 있는 값들을 뽑아서 모두 임시 큐에 삽입
                    while (pq.size() > 1) {
                        queue.add(pq.poll());
                    }
                    
                    pq.poll();  // 우선순위 큐에서 가장 마지막에 뽑은 숫자(최솟값) 삭제
                    
                    // 임시 큐가 빌 때까지
                    while (!queue.isEmpty()) {
                        // 임시 큐에 있던 값들을 뽑아서 모두 우선순위 큐에 삽입
                        pq.add(queue.poll());
                    }
                }
            }
        }
        
        if (pq.size() == 1) {   // 우선순위 큐에 남아있는 숫자가 1개라면
            answer[0] = answer[1] = pq.poll();  // 남아있는 숫자 1개는 최댓값이자 최솟값
        } else if (pq.size() > 1) { // 우선순위 큐에 남아있는 숫자가 2개 이상이라면
            answer[0] = pq.poll();  // 우선순위 큐에서 가장 먼저 뽑은 숫자: 최댓값
            
            // 우선순위 큐에 남아있는 숫자가 1개가 될 때까지 우선순위 큐에 있는 값들을 뽑기
            while (pq.size() > 1) {
                pq.poll();
            }
            
            answer[1] = pq.poll();  // 우선순위 큐에서 가장 마지막에 뽑은 숫자: 최솟값
        }
        
        return answer;  // {최댓값, 최솟값} 배열 리턴
    }
}