.programmers(이중우선순위큐)

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

 

1. 2022.04.08 시도

소요시간: 16분

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for (int i=0 ;i<operations.length; i++) {
            String each = operations[i];
            if (each.indexOf("I ") > -1) {
                int number = Integer.parseInt(each.replace("I ", ""));
                pq.offer(number);
            } else if (each.indexOf("D 1") > -1) {
                PriorityQueue<Integer> other = new PriorityQueue<>();
                for (int j=0; j< pq.size()-1; j++) {
                    other.offer(pq.poll());
                }
                pq = other;
            } else if (each.indexOf("D -1") > -1) {
                pq.poll();
            }
        }

        if (pq.size() == 0) {
            return new int[]{0,0};
        }
        
        int[] answer = new int[2];
        answer[1] = pq.poll();
        int max = 0;
        while(!pq.isEmpty()) {
            max = pq.poll();
        }
        answer[0] = max;
        
        return answer;
    }
}

풀이 접근 과정

일단 간단하게 String 파싱을 하여 분기를 작성한다.
- 숫자일때는 Integer.parseInt를 사용
- 최대/최소일때는 각각 작업을 구현한다.

최대 일때는 여러가지 방법이 있겠지만 나는 2개의 PriorityQueue를 이용하였다.

 

느낀점

• 문제를 끝까지 보자.
• 이중 큐로 풀면 아래와 같다. pq.remove()와 Collections.reverseOrder()를 사용해보는 경험을 했다.

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        PriorityQueue<Integer> rpq = new PriorityQueue<>(Collections.reverseOrder());
        
        for (int i=0 ;i<operations.length; i++) {
            String each = operations[i];
            if (each.indexOf("I ") > -1) {
                int number = Integer.parseInt(each.replace("I ", ""));
                pq.offer(number);
                rpq.offer(number);
            } else if (each.indexOf("D 1") > -1) {
                Integer target = rpq.poll();
                pq.remove(target);
            } else if (each.indexOf("D -1") > -1) {
                Integer target = pq.poll();
                rpq.remove(target);
            }
        }

        if (pq.size() == 0) {
            return new int[]{0,0};
        }
        
        int[] answer = new int[2];
        answer[0] = rpq.poll();
        answer[1] = pq.poll();
        
        return answer;
    }
}

 

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형