[프로그래머스 lv 3] 이중우선순위큐.java

<문제 설명>

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

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

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현하면 되는 문제이다.

 

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

명령어	수행할 명령
I 숫자	큐에 주어진 숫자를 삽입합니다.
D 1	큐에서 최댓값을 삭제합니다.
D -1	큐에서 최솟값을 삭제합니다.

 

입출력의 예는 다음과 같다.

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

 

<문제 풀이 아이디어>

자바의 자료구조 중 덱을 이용할 것이다.

명령어가 I일 경우와 D인 경우를 분리해서 만약 I이면 뒤의 숫자를 덱에 삽입한다. 이때 삽입하는 숫자는 최소, 최댓값과 비교해서 그 값들에 해당하는 지 확인 후 넣어준다. (최대, 최소 확인용 작업)

D일 경우는 다시 1과 -1일 경우를 분리한다. 1일 경우에는 덱에서 제일 뒤의 숫자를 제거하고 max 값도 바뀐 제일 뒤의 값으로 바꿔준다. -1일 경우는 1과 동일하나 최댓값이 아니라 최솟값이므로 덱의 제일 앞의 숫자를 제거한다.

모든 연산 이후 덱이 비었으면 최대 최소에 0을, 아니라면 현재 기준 최대 최소를 리턴한다.

 

<문제 풀이 코드>

import java.util.*;
class Solution {
    public int[] solution(String[] operations) {
        
        Deque<Integer> dq = new ArrayDeque<>();
        int max = 0;
        int min = 0;
        for(String orders: operations){
            String[] order = orders.split(" ");
            int num = Integer.parseInt(order[1]);
            if(order[0].equals("I")){
                if(dq.size()==0){
                    min = num;
                    max = num;
                    dq.add(num);
                }
                else{
                    if(num==max&num==min){
                        max = num;
                        dq.addLast(num);
                    }
                    else if(num>=max){
                        max = num;
                        dq.addLast(num);
                    }
                    else if(num<=min){
                        min = num;
                        dq.addFirst(num);
                    }
                }
            }
            else if(order[0].equals("D")){
                if(dq.size()>0){
                    if(num == 1){
                        dq.pollLast();
                        if(dq.size()>0){
                            max = dq.peekLast();
                        }
                        else{
                            max = 0;
                        }
                    }
                    else if(num == -1){
                        dq.pollFirst();
                        
                        if(dq.size()>0){
                            min = dq.peekFirst();
                        }
                        else{
                            min = 0;
                        }
                    }
                }
            }
        }
        int[] answer = new int[2];
	answer[0] = max;
	answer[1] = min;
        
        return answer;
    }
}

채점 결과