[프로그래머스] 이중우선순위큐 (Heap)

문제 소개

오늘 풀었던 프로그래머스 - 이중 우선순위 큐 문제를 정리합니다.

이 문제는 문자열로 주어진 명령어 리스트를 따라

• 숫자를 삽입 / 최댓값 또는 최솟값을 하나씩 삭제 하는 연산을 순차적으로 처리한 후,
• 큐가 비어 있으면 [0,0], 아니면 [최댓값, 최솟값]을 반환하는 문제입니다.

문제 링크: 이중우선순위큐 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 중복 값도 관리할 수 있어야 하므로 값과 개수를 함께 저장해야 함
2. 이를 위해 TreeMap<Integer, Integer> 을 사용
   • 자동 정렬: firstKey(), lastKey()로 최솟값/최댓값에 O(log N)으로 접근 가능
   • 중복 처리: value에 등장 횟수 저장
3. 연산을 순서대로 처리하면서 적절히 삽입/삭제 처리

---

해결 과정 및 코드

핵심 아이디어

 

• TreeMap은 이진 탐색 트리 기반이므로 정렬된 상태 유지
• 삽입 시 put(k, v), 삭제 시 value를 1 감소시키고 0이면 remove
• 마지막 결과에서 큐가 비어 있으면 [0,0], 아니면 [lastKey, firstKey]

 

 

코드

시간 복잡도 :O(N log N)

• N은 연산 수 (최대 1,000,000)
• 각 삽입/삭제/조회 연산은 TreeMap의 log N 시간에 수행됨

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = new int[2];
        TreeMap<Integer, Integer> tree = new TreeMap<>();

        for (String op : operations) {
            StringTokenizer st = new StringTokenizer(op);
            String cmd = st.nextToken();
            int num = Integer.parseInt(st.nextToken());

            if (cmd.equals("I")) { // 삽입
                tree.put(num, tree.getOrDefault(num, 0) + 1);
            } else if (cmd.equals("D") && !tree.isEmpty()) { //삭제
                int key = (num == 1) ? tree.lastKey() : tree.firstKey();
                if (tree.get(key) == 1) {
                    tree.remove(key);
                } else {
                    tree.put(key, tree.get(key) - 1);
                }
            }
        }

        if (!tree.isEmpty()) {
            answer[0] = tree.lastKey();
            answer[1] = tree.firstKey();
        }
        return answer;
    }
}