[프로그래머스 : 레벨 3] 이중 우선순위 큐 : PriorityQueue (Java)

이번 문제는 다행히도 답지를 보지 않았다.

내가 한 문제가 효율이 좋은지는 잘 모르겠지만 어찌됐건 성공이긴 하다.

다른 사람들의 코드를 보고 괜찮은게 있는지 보려고 했지만 나랑 별반 다를게 없었다.

 

일단 문제 부터 보자.

 

문제 설명

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

 

명령어	수신 탑(높이)
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를 반환합니다.

 

문제 해석

I 면 뒤에 있는 숫자를 삽입하고 D 1이면 최대값 삭제, D -1 이면 최소 값 삭제후

남아 있는 숫자중 최대값과 최소값을 출력해라

단 남아 있는 값이 없다면 [0,0]을 return 하라

 

나의 소스는 아래와 같다.

 

    public int[] solution(String[] operations) {
        int[] answer = {};
        int len = operations.length;
        
        List<Integer> result = new ArrayList<>();
        
        PriorityQueue<Integer> up = new PriorityQueue<>();
        PriorityQueue<Integer> down = new PriorityQueue<>(Collections.reverseOrder());
        
        for(int i = 0; i<len;i++){
            String[] sp = operations[i].split(" ");
            
            String front = sp[0];
            
            switch(front) {
	            case "I" :
	            	int num = Integer.parseInt(sp[1]);
	            	
	            	up.offer(num);
	            	down.offer(num);
	            	result.add(num);
	            	
	            	break;
	            case "D" :
	            	String second = sp[1];
	            	switch(second) {
		            	case "-1": //최소값을 삭제해야함
		            		if(result.isEmpty()) {
		            			break;
		            		}
		            		int min = up.poll();
		            		down.clear(); //삭제하고 다시 넣어야함
		            		for(int idx = 0;idx<result.size();idx++) {
		            			if(result.get(idx) == min) {//해당 값 삭제
		            				result.remove(idx);
		            				idx-=1;
		            			}else {//나머지는 내림차순에 다시 넣음
		            				down.offer(result.get(idx));
		            			}
		            		}
		            		break;
		            	case "1": //최대값을 삭제해야함
		            		if(result.isEmpty()) {
		            			break;
		            		}
		            		int max = down.poll();
		            		up.clear(); //삭제하고 다시 넣어야함
		            		for(int idx = 0;idx<result.size();idx++) {
		            			if(result.get(idx) == max) { //해당 값 삭제
		            				result.remove(idx);
		            				idx -=1;
		            			}else {//나머지는 오름차순에 다시 넣음
		            				up.offer(result.get(idx));
		            			}
		            		}
		            		break;
	            	}
	            	break;
            	
            }

        }
        
       answer = new int[2];
        
        if(result.isEmpty()){
            answer[0] = 0;
            answer[1] = 0;
        }else {
            answer[0] = down.poll();
            answer[1] = up.poll();
        }
        
        System.out.println(Arrays.toString(answer));
        
        return answer;
    }

 

일단 해당 문자열을 " "로 split 해서 배열에 담고 

첫번째 sp[0] 에 따라서 삽입과 삭제를 나눴다.

그리고 삭제의 경우에는 sp[1]을 "-1 과 "1" 로 나눠서 최대값 삭제와 최소값 삭제를 구분했고

그 안에서는 최대값인 경우 최대값을 poll()해와서 해당 값을 지우고 다시 집어 넣는 역할을 했다.

 

느낀점

1. switch안에 switch를 사용이 가능하다

2. 문제를 자세히 읽어보자.