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

Algorithm/코딩테스트

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

ioh'sDeveloper 2024. 5. 26. 22:09

💡 문제
이중우선순위큐 (https://school.programmers.co.kr/learn/courses/30/lessons/42628)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

📝 선행 개념

이중 우선순위 큐는 최댓값과 최솟값을 모두 효율적으로 처리할 수 있는 자료구조

Collections.reverseOrder()

Collections.reverseOrder()는 Java의 Collections 클래스에서 제공하는 정적 메서드로, 기본 정렬 순서를 반대로 하는 데 사용됩니다. 이 메서드는 Comparator 객체를 반환하며, 이 객체를 사용하여 컬렉션을 내림차순으로 정렬할 수 있습니다. 이는 기본 데이터 타입뿐만 아니라 커스텀 객체에도 적용할 수 있으며, Comparable 인터페이스를 구현하여 객체의 정렬 기준을 정의해야 합니다.

예제 및 설명

기본적으로 Collections.reverseOrder()는 자연 순서를 기준으로 내림차순 정렬을 수행합니다. 예를 들어, 숫자나 문자열의 경우 기본적으로 오름차순으로 정렬되지만, reverseOrder()를 사용하면 내림차순으로 정렬됩니다.

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> numbers = Arrays.asList(1, 3, 5, 2, 4);

        // 기본 오름차순 정렬
        Collections.sort(numbers);
        System.out.println("오름차순 정렬: " + numbers);

        // 내림차순 정렬
        Collections.sort(numbers, Collections.reverseOrder());
        System.out.println("내림차순 정렬: " + numbers);
    }
}

위 예제에서, 먼저 Collections.sort(numbers)를 사용하여 리스트를 오름차순으로 정렬한 후, Collections.sort(numbers, Collections.reverseOrder())를 사용하여 리스트를 내림차순으로 정렬합니다.

커스텀 객체 정렬

Collections.reverseOrder()는 커스텀 객체를 정렬할 때도 사용할 수 있습니다. 이 경우 객체가 Comparable 인터페이스를 구현하고 있어야 합니다.

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Person implements Comparable<Person> {
    String name;
    int age;

    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int compareTo(Person other) {
        return this.age - other.age; // 나이 오름차순으로 정렬
    }

    @Override
    public String toString() {
        return name + ": " + age;
    }
}

public class Main {
    public static void main(String[] args) {
        List<Person> people = Arrays.asList(
            new Person("Alice", 30),
            new Person("Bob", 25),
            new Person("Charlie", 35)
        );

        // 나이 오름차순 정렬
        Collections.sort(people);
        System.out.println("나이 오름차순 정렬: " + people);

        // 나이 내림차순 정렬
        Collections.sort(people, Collections.reverseOrder());
        System.out.println("나이 내림차순 정렬: " + people);
    }
}

위 예제에서, Person 객체는 나이에 따라 오름차순으로 정렬됩니다. Collections.reverseOrder()를 사용하여 내림차순으로 정렬할 수 있습니다.

🤓 문제 풀이

최댓값과 최솟값을 효율적으로 삭제
- "D 1 큐에서 최댓값을 삭제합니다."
- "D -1 큐에서 최솟값을 삭제합니다."
큐에서 최댓값과 최솟값을 빠르게 찾고 삭제
- "이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요."
숫자를 큐에 삽입 (I 숫자). 큐에서 최댓값을 삭제 (D 1). 큐에서 최솟값을 삭제 (D -1). 이러한 연산을 효율적으로 처리하려면 최댓값과 최솟값을 빠르게 접근하고 삭제할 수 있어야 하는데 이를 위해 힙 자료구조를 사용

이 문장에서 최댓값과 최솟값을 빠르게 찾고 삭제할 필요가 있다는 점을 알 수 있습니다. 힙(Heap) 자료구조는 이러한 작업을 효율적으로 수행할 수 있는 자료구조입니다.

각 연산은 큐에 요소를 삽입하거나 최댓값 또는 최솟값을 삭제하는 것이기 때문에, 이를 효율적으로 처리하기 위해 두 개의 우선순위 큐를 사용합니다. 하나는 최소 힙으로, 다른 하나는 최대 힙으로 구현합니다. 이를 통해 최솟값과 최댓값을 효율적으로 추출하고 삭제할 수 있습니다.

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 오름차순(최솟값)으로 정렬
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // 내림차순(최댓값)으로 정렬

        for (String operation : operations) {
            String[] parts = operation.split(" "); // 명령어와 값을 분리
            String command = parts[0]; // 명령어 ("I" 또는 "D")
            int value = Integer.parseInt(parts[1]); // 숫자

            if (command.equals("I")) { // 삽입 연산
                minHeap.add(value); // 최소 힙에 삽입
                maxHeap.add(value); // 최대 힙에 삽입
            } else if (command.equals("D")) { // 삭제 연산
                if (value == 1 && !maxHeap.isEmpty()) { // 최댓값 삭제
                    int maxValue = maxHeap.poll(); // 최댓값 추출
                    minHeap.remove(maxValue); // 최소 힙에서 삭제
                } else if (value == -1 && !minHeap.isEmpty()) { // 최솟값 삭제
                    int minValue = minHeap.poll(); // 최솟값 추출
                    maxHeap.remove(minValue); // 최대 힙에서 삭제
                }
            }
        }

        if (minHeap.isEmpty() || maxHeap.isEmpty()) {
            return new int[]{0, 0}; // 큐가 비어있는 경우 [0, 0] 반환
        } else {
            return new int[]{maxHeap.peek(), minHeap.peek()}; // 비어있지 않은 경우 [최댓값, 최솟값] 반환
        }
    }

}

📚 풀이 보완

코드 설명

1. PriorityQueue (우선순위 큐)

최소 힙과 최대 힙을 각각 사용하여 최솟값과 최댓값 관리
PriorityQueue<Integer> minHeap = new PriorityQueue<>();: 기본적으로 오름차순(최솟값)으로 정렬되는 최소 힙을 선언합니다.
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());: 내림차순(최댓값)으로 정렬되는 최대 힙을 선언합니다.

2. syncSet 사용:

Set<Integer> syncSet = new HashSet<>();: 삽입된 요소를 추적하기 위해 동기화 집합을 사용합니다. 이를 통해 힙 간의 동기화를 유지합니다.
연산 처리:
- 각 연산을 operations 배열에서 하나씩 처리합니다.
- "I 숫자" 연산:
  - minHeap, maxHeap 및 syncSet에 숫자를 삽입합니다.
- "D 1" 연산:
  - maxHeap에서 유효한 최댓값을 추출하고, syncSet과 minHeap에서 해당 값을 제거합니다.
- "D -1" 연산:
  - minHeap에서 유효한 최솟값을 추출하고, syncSet과 maxHeap에서 해당 값을 제거합니다.

이 코드는 두 개의 우선순위 큐(최소 힙과 최대 힙)를 사용하여 이중 우선순위 큐의 동작을 구현합니다. 각 연산은 효율적으로 수행되며, 최종적으로 큐의 상태에 따라 적절한 결과를 반환합니다.

📍 Plus+

add() 및 offer() 차이점

add() 및 **offer()**는 Java의 Queue 인터페이스에서 모두 사용 가능한 메서드로, 요소를 큐에 추가합니다. 두 메서드의 주요 차이점은 큐가 가득 찬 경우에 발생합니다.

add() 메서드:
- 큐가 가득 찬 경우 (용량 초과), IllegalStateException을 발생시킵니다.
- 따라서 add() 메서드를 사용할 때는 큐가 가득 찬 상태를 확인하고 예외 처리를 해주어야 합니다.
offer() 메서드:
- 큐가 가득 찬 경우 (용량 초과), false를 반환합니다.
- 예외를 발생시키지 않고 실패를 알려주기 때문에, 보다 안전하게 요소를 추가할 수 있습니다.

따라서 일반적으로 용량 초과가 발생할 가능성이 있는 상황에서는 offer() 메서드를 사용하는 것이 안전하고 좋습니다. 위 코드에서 offer() 메서드를 사용한 이유는 큐가 용량을 초과하는 경우를 고려하여 안전하게 요소를 추가하기 위함입니다.

이중 우선순위 큐 문제 접근 방법

이중 우선순위 큐는 최댓값과 최솟값을 모두 효율적으로 처리할 수 있는 자료구조입니다. 이중 우선순위 큐는 다음과 같은 연산을 지원합니다:

삽입 (I 숫자): 큐에 숫자를 삽입합니다.
삭제 (D 1): 큐에서 최댓값을 삭제합니다.
삭제 (D -1): 큐에서 최솟값을 삭제합니다.

이 자료구조는 일반적으로 두 개의 우선순위 큐를 사용하여 구현됩니다: 하나는 최솟값을 추적하기 위한 최소 힙(min-heap), 다른 하나는 최댓값을 추적하기 위한 최대 힙(max-heap)입니다.

문제 접근 방법

이 문제를 해결하기 위해서는 다음과 같은 전략을 사용할 수 있습니다:

삽입 연산 (I 숫자):
- 주어진 숫자를 최소 힙과 최대 힙에 삽입합니다.
삭제 연산 (D 1):
- 최대 힙에서 최댓값을 삭제합니다.
- 이 때, 최소 힙에서 해당 값을 동기화합니다.
삭제 연산 (D -1):
- 최소 힙에서 최솟값을 삭제합니다.
- 이 때, 최대 힙에서 해당 값을 동기화합니다.
동기화:
- 삭제 연산 후 두 힙을 동기화하여 일관된 상태를 유지합니다.

import java.util.*;

class Solution {
    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 command = parts[0];
            int number = Integer.parseInt(parts[1]);

            if (command.equals("I")) {
                // 삽입 연산
                minHeap.offer(number);
                maxHeap.offer(number);
                countMap.put(number, countMap.getOrDefault(number, 0) + 1);
            } else {
                // 삭제 연산
                if (number == 1) {
                    // 최댓값 삭제
                    remove(maxHeap, countMap);
                } else {
                    // 최솟값 삭제
                    remove(minHeap, countMap);
                }
            }
        }
        
        // 두 힙을 동기화하여 남아 있는 요소를 얻음
        remove(minHeap, countMap);
        remove(maxHeap, countMap);
        
        if (countMap.isEmpty()) {
            return new int[]{0, 0};
        } else {
            int max = remove(maxHeap, countMap);
            int min = remove(minHeap, countMap);
            return new int[]{max, min};
        }
    }
    
    private int remove(PriorityQueue<Integer> heap, HashMap<Integer, Integer> countMap) {
        while (!heap.isEmpty()) {
            int value = heap.poll();
            int count = countMap.getOrDefault(value, 0);
            if (count > 0) {
                countMap.put(value, count - 1);
                if (count - 1 == 0) {
                    countMap.remove(value);
                }
                return value;
            }
        }
        return 0;
    }
}

코드 설명

PriorityQueue:
- minHeap: 최소 힙으로 사용됩니다.
- maxHeap: 최대 힙으로 사용됩니다.
HashMap:
- countMap: 각 숫자의 삽입 횟수를 저장합니다. 이는 힙에서 동기화할 때 사용됩니다.
연산 처리:
- 삽입: **minHeap**과 **maxHeap**에 숫자를 삽입하고 **countMap**에 삽입 횟수를 증가시킵니다.
- 삭제: 최댓값 삭제(maxHeap)와 최솟값 삭제(minHeap)을 수행할 때 **countMap**을 참고하여 실제로 존재하는 숫자를 제거합니다.
결과 반환:
- 모든 연산을 처리한 후, 두 힙을 동기화하여 남아 있는 최댓값과 최솟값을 구합니다.
- 큐가 비어 있으면 **[0, 0]**을 반환하고, 그렇지 않으면 **[최댓값, 최솟값]**을 반환합니다.

이중 우선순위 큐의 핵심은 두 힙을 사용하여 최댓값과 최솟값을 효율적으로 추적하고, 삽입과 삭제 연산을 동기화하는 것입니다.

'Algorithm > 코딩테스트' 카테고리의 다른 글

[리트코드][JAVA] 899. orderly-queue (정렬된 큐) (0)	2024.05.27
[리트코드][JAVA] 2551. Put Marbles in Bags (구슬을 가방에 담다) (0)	2024.05.26
[프로그래머스][JAVA] 디스크 컨트롤러 (0)	2024.05.26
[프로그래머스][JAVA] 주식 가격 (0)	2024.05.23
[프로그래머스][JAVA] 다리를 지나는 트럭 (0)	2024.05.23

현재글[프로그래머스][JAVA] 이중 우선순위 큐

ioh's Development

Back-End 주니어 개발자 입니다. 개발이 재밌는 사람입니다만... :D

프로그래머를위한기초수학, 알고리즘, dfs, 수학리부트, 프로그래머스, BFS, heap, 정렬된큐, 99클럽, java, 코딩테스트, 개발자스터디, 정렬, 개발자수학, 99일지, Queue, til, 자료구조, 디스크컨트롤러, 항해,

Today :
Yesterday :

일	월	화	수	목	금	토
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30	31

ioh's Development