[프로그래머스] 이중우선순위

[코딩테스트]

[프로그래머스] 이중우선순위

everydeveloper 2024. 6. 7. 13:08

아까 문제 너무 어려워서 이문제 풀려고 해

이 문제는 이중 우선순위 큐를 구현하여 주어진 연산을 처리하고, 결과를 반환하는 것입니다. 이중 우선순위 큐는 최대값과 최소값을 효율적으로 삽입 및 삭제할 수 있어야 합니다.

문제 해결 접근법

데이터 구조 선택:
- Python의 heapq 모듈을 사용하여 최소 힙을 구현할 수 있습니다. 하지만 최대 힙과 최소 힙을 동시에 구현하여 최대값과 최소값을 효율적으로 삭제할 수 있도록 합니다.
- 두 개의 힙을 사용합니다: 최소 힙(min_heap)과 최대 힙(max_heap).
연산 처리:
- I 숫자: 주어진 숫자를 두 힙에 모두 삽입합니다.
- D 1: 최대 힙에서 최대값을 삭제합니다.
- D -1: 최소 힙에서 최소값을 삭제합니다.
동기화 문제 해결:
- 하나의 힙에서 값을 삭제할 때 다른 힙에서도 해당 값을 삭제해야 합니다. 이를 위해 삽입한 값을 추적할 수 있는 자료 구조가 필요합니다.

예제 코드

아래는 문제를 해결하기 위한 예제 코드입니다:

import heapq

def solution(operations):
    min_heap = []
    max_heap = []
    entry_finder = {}  # 각 값을 추적하기 위한 딕셔너리
    REMOVED = '<removed>'  # 삭제된 항목을 표시하기 위한 표식

    def add_number(num):
        if num in entry_finder:
            entry_finder[num] += 1
        else:
            entry_finder[num] = 1
        heapq.heappush(min_heap, num)
        heapq.heappush(max_heap, -num)

    def remove_max():
        while max_heap:
            num = -heapq.heappop(max_heap)
            if entry_finder.get(num, 0) > 0:
                entry_finder[num] -= 1
                break

    def remove_min():
        while min_heap:
            num = heapq.heappop(min_heap)
            if entry_finder.get(num, 0) > 0:
                entry_finder[num] -= 1
                break

    for operation in operations:
        if operation[0] == 'I':
            num = int(operation[2:])
            add_number(num)
        elif operation == 'D 1':
            remove_max()
        elif operation == 'D -1':
            remove_min()

    min_result, max_result = 0, 0
    while min_heap:
        num = heapq.heappop(min_heap)
        if entry_finder.get(num, 0) > 0:
            min_result = num
            break

    while max_heap:
        num = -heapq.heappop(max_heap)
        if entry_finder.get(num, 0) > 0:
            max_result = num
            break

    return [max_result, min_result]

# 예시 테스트
operations = ["I 16", "D 1", "I -5643", "D -1", "I 123", "D -1"]
print(solution(operations))  # [0, 0]

operations = ["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"]
print(solution(operations))  # [333, -45]

코드 설명

추가 연산 (I 숫자):
- add_number(num) 함수를 호출하여 주어진 숫자를 최소 힙과 최대 힙에 삽입합니다.
- entry_finder 딕셔너리를 사용하여 각 숫자가 몇 번 삽입되었는지 추적합니다.
최대값 삭제 (D 1):
- remove_max() 함수를 호출하여 최대 힙에서 최대값을 삭제합니다.
- 힙에서 삭제된 값을 entry_finder에서 감소시킵니다.
최소값 삭제 (D -1):
- remove_min() 함수를 호출하여 최소 힙에서 최소값을 삭제합니다.
- 힙에서 삭제된 값을 entry_finder에서 감소시킵니다.
최종 결과 계산:
- 최소 힙과 최대 힙에서 남아있는 값 중 유효한 값을 찾아서 반환합니다.

이 접근법을 사용하면 이중 우선순위 큐를 효율적으로 구현할 수 있습니다.

이 문제 설명을 보고 설명 해줘 쉽게

이중 우선순위 큐 문제는 큐를 사용하여 최대값과 최소값을 효율적으로 삽입하고 삭제하는 자료 구조를 구현하는 문제입니다. 이 문제에서는 주어진 연산 목록을 처리하여 최종 결과를 반환해야 합니다.

문제 설명 요약

이 문제에서는 다음과 같은 세 가지 연산을 수행할 수 있는 큐를 구현해야 합니다:

I 숫자 - 큐에 주어진 숫자를 삽입합니다.
D 1 - 큐에서 최대값을 삭제합니다.
D -1 - 큐에서 최소값을 삭제합니다.

입력 예시

operations = ["I 16", "D 1", "I -5643", "D -1", "I 123", "D -1"]

제한사항

operations의 길이는 1 이상 1,000,000 이하입니다.
각 연산은 "I 숫자" 또는 "D 1" 또는 "D -1"의 형식으로 주어집니다.
빈 큐에서 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

처리 과정

숫자 삽입 (I 숫자):
- 주어진 숫자를 큐에 삽입합니다.
최대값 삭제 (D 1):
- 큐에서 최대값을 삭제합니다.
- 큐가 비어있으면 이 연산은 무시됩니다.
최소값 삭제 (D -1):
- 큐에서 최소값을 삭제합니다.
- 큐가 비어있으면 이 연산은 무시됩니다.

결과

모든 연산을 처리한 후, 큐가 비어있으면 [0, 0]을 반환합니다. 그렇지 않으면 [최대값, 최소값]을 반환합니다.

예제 코드

아래는 Python으로 이중 우선순위 큐를 구현한 예제 코드입니다:

import heapq

def solution(operations):
    min_heap = []
    max_heap = []
    entry_finder = {}  # 각 값을 추적하기 위한 딕셔너리

    def add_number(num):
        if num in entry_finder:
            entry_finder[num] += 1
        else:
            entry_finder[num] = 1
        heapq.heappush(min_heap, num)
        heapq.heappush(max_heap, -num)

    def remove_max():
        while max_heap:
            num = -heapq.heappop(max_heap)
            if entry_finder.get(num, 0) > 0:
                entry_finder[num] -= 1
                break

    def remove_min():
        while min_heap:
            num = heapq.heappop(min_heap)
            if entry_finder.get(num, 0) > 0:
                entry_finder[num] -= 1
                break

    for operation in operations:
        if operation[0] == 'I':
            num = int(operation[2:])
            add_number(num)
        elif operation == 'D 1':
            remove_max()
        elif operation == 'D -1':
            remove_min()

    min_result, max_result = 0, 0
    while min_heap:
        num = heapq.heappop(min_heap)
        if entry_finder.get(num, 0) > 0:
            min_result = num
            break

    while max_heap:
        num = -heapq.heappop(max_heap)
        if entry_finder.get(num, 0) > 0:
            max_result = num
            break

    return [max_result, min_result]

# 예시 테스트
operations = ["I 16", "D 1", "I -5643", "D -1", "I 123", "D -1"]
print(solution(operations))  # [0, 0]

operations = ["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"]
print(solution(operations))  # [333, -45]

코드 설명

추가 연산 (I 숫자):
- 주어진 숫자를 최소 힙과 최대 힙에 삽입합니다.
- entry_finder 딕셔너리를 사용하여 각 숫자가 몇 번 삽입되었는지 추적합니다.
최대값 삭제 (D 1):
- 최대 힙에서 최대값을 삭제합니다.
- entry_finder에서 삭제된 값을 감소시킵니다.
최소값 삭제 (D -1):
- 최소 힙에서 최소값을 삭제합니다.
- entry_finder에서 삭제된 값을 감소시킵니다.
최종 결과 계산:
- 최소 힙과 최대 힙에서 남아있는 값 중 유효한 값을 찾아서 반환합니다.

이와 같이 이중 우선순위 큐를 구현하여 주어진 연산을 처리할 수 있습니다.

뭐야 이거 구현 문제야? 범주에는 힙이라고 되어 있는데....순서대로 값 넣고 최대 값이나 최소값 삭제가 있으면 그부분 구현하고 실행하고 계속 명령 반복하다가 최대값이나 최소값 배열로 보여주면 되는 거잖아 코딩 문제 같기도 하고 처음에 이해하기 어려웠네

네, 이 문제는 이중 우선순위 큐를 구현하는 문제입니다. 기본적으로 힙 자료 구조를 이용하여 최대값과 최소값을 효율적으로 삽입하고 삭제하는 기능을 구현해야 합니다. 이 문제를 해결하기 위해서는 힙(heap)을 사용하여 주어진 명령어를 순서대로 처리하고, 최종적으로 큐에 남아있는 최대값과 최소값을 반환하면 됩니다.

문제 해결 접근법

힙 자료 구조 사용:
- Python의 heapq 모듈을 사용하여 최소 힙(min-heap)을 구현할 수 있습니다.
- 최대 힙(max-heap)은 음수 값을 이용하여 heapq를 사용하여 구현할 수 있습니다.
명령어 처리:
- I 숫자: 주어진 숫자를 최소 힙과 최대 힙에 삽입합니다.
- D 1: 최대 힙에서 최대값을 삭제합니다.
- D -1: 최소 힙에서 최소값을 삭제합니다.
정합성 유지:
- 하나의 힙에서 값을 삭제할 때 다른 힙에서도 해당 값을 삭제해야 합니다. 이를 위해 삽입한 값을 추적할 수 있는 자료 구조가 필요합니다.

예제 코드

아래는 Python으로 이중 우선순위 큐를 구현한 예제 코드입니다:

import heapq

def solution(operations):
    min_heap = []
    max_heap = []
    entry_finder = {}  # 각 값을 추적하기 위한 딕셔너리
    REMOVED = '<removed>'  # 삭제된 항목을 표시하기 위한 표식

    def add_number(num):
        if num in entry_finder:
            entry_finder[num] += 1
        else:
            entry_finder[num] = 1
        heapq.heappush(min_heap, num)
        heapq.heappush(max_heap, -num)

    def remove_max():
        while max_heap:
            num = -heapq.heappop(max_heap)
            if entry_finder.get(num, 0) > 0:
                entry_finder[num] -= 1
                break

    def remove_min():
        while min_heap:
            num = heapq.heappop(min_heap)
            if entry_finder.get(num, 0) > 0:
                entry_finder[num] -= 1
                break

    for operation in operations:
        if operation[0] == 'I':
            num = int(operation[2:])
            add_number(num)
        elif operation == 'D 1':
            remove_max()
        elif operation == 'D -1':
            remove_min()

    min_result, max_result = 0, 0
    while min_heap:
        num = heapq.heappop(min_heap)
        if entry_finder.get(num, 0) > 0:
            min_result = num
            break

    while max_heap:
        num = -heapq.heappop(max_heap)
        if entry_finder.get(num, 0) > 0:
            max_result = num
            break

    return [max_result, min_result]

# 예시 테스트
operations = ["I 16", "D 1", "I -5643", "D -1", "I 123", "D -1"]
print(solution(operations))  # [0, 0]

operations = ["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"]
print(solution(operations))  # [333, -45]

코드 설명

추가 연산 (I 숫자):
- 주어진 숫자를 최소 힙과 최대 힙에 삽입합니다.
- entry_finder 딕셔너리를 사용하여 각 숫자가 몇 번 삽입되었는지 추적합니다.
최대값 삭제 (D 1):
- 최대 힙에서 최대값을 삭제합니다.
- entry_finder에서 삭제된 값을 감소시킵니다.
최소값 삭제 (D -1):
- 최소 힙에서 최소값을 삭제합니다.
- entry_finder에서 삭제된 값을 감소시킵니다.
최종 결과 계산:
- 최소 힙과 최대 힙에서 남아있는 값 중 유효한 값을 찾아서 반환합니다.

문제 해결 요약

힙 자료 구조를 사용하여 최소값과 최대값을 효율적으로 관리합니다.
각 명령을 순서대로 처리하여 힙에 숫자를 삽입하고, 최대값 및 최소값을 삭제합니다.
모든 명령을 처리한 후, 힙에 남아 있는 값 중 유효한 최대값과 최소값을 찾아 반환합니다.

이와 같이 이중 우선순위 큐를 구현하여 주어진 명령을 처리하고 최종 결과를 도출할 수 있습니다.

음 이문제를 자바로 구현해줘 그리고 힙 자료 구조는 뭐야? 난 그것 몰라

힙(heap) 자료 구조는 특정 규칙을 만족하는 이진 트리입니다. 힙은 최댓값이나 최솟값을 빠르게 찾기 위해 사용되며, 대표적으로 최대 힙과 최소 힙이 있습니다.

최대 힙(Max Heap): 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리.
최소 힙(Min Heap): 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리.

힙은 우선순위 큐(priority queue)로 구현되며, 삽입과 삭제 연산이 모두 \(O(\log n)\) 시간 복잡도를 가집니다.

이제 자바로 이 문제를 해결하는 방법을 설명하겠습니다.

자바로 이중 우선순위 큐 구현

두 개의 우선순위 큐 사용:
- 하나는 최소 힙 (최소값을 관리)
- 하나는 최대 힙 (최대값을 관리)
연산 처리:
- I 숫자: 숫자를 두 힙에 모두 삽입.
- D 1: 최대 힙에서 최대값 삭제.
- D -1: 최소 힙에서 최소값 삭제.
동기화 문제 해결:
- 하나의 힙에서 값을 삭제할 때 다른 힙에서도 해당 값을 삭제해야 하므로, 삽입된 숫자를 추적할 수 있는 자료 구조가 필요합니다.

자바 코드 구현

import java.util.Collections;
import java.util.PriorityQueue;
import java.util.HashMap;

public class DualPriorityQueue {
    public int[] solution(String[] operations) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        HashMap<Integer, Integer> countMap = new HashMap<>();

        for (String operation : operations) {
            String[] parts = operation.split(" ");
            String op = parts[0];
            int num = Integer.parseInt(parts[1]);

            if (op.equals("I")) {
                minHeap.add(num);
                maxHeap.add(num);
                countMap.put(num, countMap.getOrDefault(num, 0) + 1);
            } else if (op.equals("D")) {
                if (num == 1) {
                    removeElement(maxHeap, countMap);
                } else {
                    removeElement(minHeap, countMap);
                }
            }
        }

        while (!minHeap.isEmpty() && countMap.get(minHeap.peek()) == 0) {
            minHeap.poll();
        }
        while (!maxHeap.isEmpty() && countMap.get(maxHeap.peek()) == 0) {
            maxHeap.poll();
        }

        int max = maxHeap.isEmpty() ? 0 : maxHeap.peek();
        int min = minHeap.isEmpty() ? 0 : minHeap.peek();

        return new int[]{max, min};
    }

    private void removeElement(PriorityQueue<Integer> heap, HashMap<Integer, Integer> countMap) {
        while (!heap.isEmpty()) {
            int num = heap.poll();
            if (countMap.get(num) > 0) {
                countMap.put(num, countMap.get(num) - 1);
                break;
            }
        }
    }

    public static void main(String[] args) {
        DualPriorityQueue dpq = new DualPriorityQueue();
        String[] operations1 = {"I 16", "D 1", "I -5643", "D -1", "I 123", "D -1"};
        int[] result1 = dpq.solution(operations1);
        System.out.println("Result: [" + result1[0] + ", " + result1[1] + "]");

        String[] operations2 = {"I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"};
        int[] result2 = dpq.solution(operations2);
        System.out.println("Result: [" + result2[0] + ", " + result2[1] + "]");
    }
}

코드 설명

PriorityQueue 사용:
- minHeap: 기본적으로 최소 힙으로 동작합니다.
- maxHeap: Collections.reverseOrder()를 사용하여 최대 힙으로 동작하도록 설정합니다.
명령어 처리:
- 삽입 연산(I 숫자): 숫자를 두 힙에 삽입하고, countMap에 삽입 횟수를 기록합니다.
- 삭제 연산(D 1, D -1): 최대값 삭제는 maxHeap에서, 최소값 삭제는 minHeap에서 처리합니다. 힙에서 값을 꺼낼 때마다 countMap을 확인하여 유효한 값인지 검증합니다.
최종 결과 계산:
- 힙이 비어있지 않다면 유효한 최소값과 최대값을 반환합니다. 힙이 비어있다면 [0, 0]을 반환합니다.

이와 같이, 힙 자료 구조를 사용하여 이중 우선순위 큐를 구현하고, 주어진 명령을 처리하여 최종 결과를 반환할 수 있습니다.