10. 이중 우선순위 큐 (프로그래머스, 힙 Level 3)

* 문제 설명

  이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

명령어	수신 탑(높이)
I 숫자	큐에 주어진 숫자를 삽입합니다.
D 1	큐에서 최댓값을 삭제합니다.
D -1	큐에서 최솟값을 삭제합니다.

  이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때,

  모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록

  solution 함수를 구현해주세요.

 

* 제한사항

  operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.

  operations의 원소는 큐가 수행할 연산을 나타냅니다.
  원소는 “명령어 데이터” 형식으로 주어집니다.

   - 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
  빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

 

*입출력 예

operations	return
["I 16","D 1"]	[0,0]
["I 7","I 5","I -5","D -1"]	[7,5]

 

* 입출력 예 설명

  16을 삽입 후 최댓값을 삭제합니다. 비어있으므로 [0,0]을 반환합니다.
  7,5,-5를 삽입 후 최솟값을 삭제합니다. 최대값 7, 최소값 5를 반환합니다.

 

 

이번 문제는 주어진 데이터에서 문자열을 가져온 뒤에 "숫자"와 "연산방법"을 가려낸 뒤에 해당 행위를 해야하는 문제 입니다.

 

문제의 조건을 살펴보면,

 1. 데이터를 "I" 라는 기호에 의해서 삽입을 하여 줍니다.

 2. 그러한 데이터는 "최댓값 삭제" 또는 "최솟값 삭제" 라는 기호에 맞추어 데이터가 제거 되어야 합니다.

크게 2가지로 구분되어집니다.

 

만약 0부터 50까지 순서에 맞추어 데이터가 쌓여있다고 존재 한 다면,

그중에서 최소값 5개 삭제, 최대값 5개 삭제를 하면 5 ~ 45까지의 데이터가 존재하게 될 것 입니다.

 

해당 문제를 해결하기 위해서 여러방법을 시도하여 보았지만 순수한 "배열"로 해결하기에는 다소 어려웠던 것 같습니다.

자바의 특성상 배열에서의 크기를 늘리고 줄이는 것이 쉽지 않았기 때문 입니다.

 

문제를 이해하기 위해서 먼저 데이터에 대해서 반복문을 통해 행동을 분리하여 줍니다.

public static int[] solution() {
    String operations [] = {"I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"}; 
    
    for(String arg : operations){
        if(arg.indexOf("D") > -1){  //최대 및 최소값 빼기를 하라는 문자열
        
        } else {  //I 기호, 데이터를 넣으라는 문자열
        
        }
    }
}    

 

간단한 반복문과 조건문이 완성 되었습니다.

if 조건문에 의해서 해당되는 문자열은 연산행위를 하게 될 것입니다.

else 조건문에 의해서 해당되는 문자열은 데이터가 쌓이게 될 것 입니다.

 

그러면 여기서 고민하였던 것은 바로 데이터를 어떻게 쌓고 어떻게 정렬할 것 인가라는 문제 였습니다.

왜냐하면 operations의 값이 1백만개 까지 될 수 있다고 "제한사항"에 나와있기 때문 입니다.

많은 데이터를 빠르고 효율적으로 넣으며 정렬하려면 어떻게 해야되는지 고민하던 중 예전에 사용하였던 우선순위 큐가 생각나서 사용을 해 보았습니다.

import java.util.PriorityQueue;

public class DoubleQueue {

    public static int[] solution() {
        String operations [] = {"I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"}; 
        
        PriorityQueue<Integer> que = new PriorityQueue<>();  //데이터를 쌓고 정렬하는 큐 입니다.
    
        for(String arg : operations){
            if(arg.indexOf("D") > -1){  //최대 및 최소값 빼기를 하라는 문자열
            
                //데이터를 더하고 빼야합니다.
                
            } else {  //I 기호, 데이터를 넣으라는 문자열
                int data = Integer.parseInt(arg.substring(arg.indexOf(" "), arg.length()).trim());
                que.add(data);
            }
        }
    }    
}

 

데이터를 넣는 것 까지는 훌륭하게 완성 되었습니다.

한번 출력 해 보도록 합니다.

역시 훌륭 합니다..

 

이제 남은 것은 "D 1"또는 "D -1"부호에 맞추어서 데이터를 넣고 빼는 것 입니다.

현재 우선순위큐는 오름차순으로 정렬되어 있습니다.

 

큐(queue)에서 데이터를 빼주면(poll) 가장 첫번째 데이터가 제거 될 것 입니다.(최소값)

그리고 최대값을 구하려면 큐(queue)에서 가장 큰 값을 가져와서 해당 큐에서 제거하면 될 것 입니다.

import java.util.PriorityQueue;

public class DoubleQueue {

    public static int[] solution() {
        String operations [] = {"I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"}; 
        
        PriorityQueue<Integer> que = new PriorityQueue<>();  //데이터를 쌓고 정렬하는 큐 입니다.
    
        for(String arg : operations){
            if(arg.indexOf("D") > -1){  //최대 및 최소값 빼기를 하라는 문자열
            
                String todo = arg.substring(arg.indexOf(" "), arg.length()).trim();
                if(que.size() > 0){
                    if(todo.equals("1")){  //최대값 빼기
                        Integer LastValue = que.stream().mapToInt(to->to).max().getAsInt();
                        que.remove(LastValue);
                    } else {  //최소값 빼기
                        que.poll();
                    }
                }

            } else {  //I 기호, 데이터를 넣으라는 문자열
                int data = Integer.parseInt(arg.substring(arg.indexOf(" "), arg.length()).trim());
                que.add(data);
            }
        }
    }    
}

 

정말 행복하게도 우선순위큐(PriorityQueue)는 컬렉션(Collection)이 부모입니다.

컬렉션에서 사용가능한 스트림을 활용하여 큐의 가장 큰 값을 가져올 수 있으며, 가장 큰 값을 remove라는 메소드를 통해 제거 할 수 있습니다.

이제 코드를 제출하여 봅니다.

통과입니다!!

 

포스팅에서는 쉽게 한 것으로 적고 있지만, 순수 배열만 사용해서 문제를 해결해 보려고 하였으나 그렇지 못해서 너무 아쉬웠던 것 같습니다.

이상으로 프로그래머스 문제인 "이중우선순위큐"에 대해서 살펴 보았습니다.

궁금한 점 또는 문의사항은 언제든 연락주세요. :)