[자료구조] 비선형 자료구조 : 우선순위 큐 - 연습문제

연습문제1. 정수로 이뤄진 배열 중 k번째로 큰 정수 찾아내기

정수로 이뤄진 배열 numbers에서, k번째로 큰 정수를 찾아내기.

 

방법1. 우선순위 큐를 통하여 우선적으로 큰 수부터 출력 후에 k번째 출력을 찾아내기

minHeap으로 풀어주기

이렇게 위에서부터 아래로 내려가면서 오름차순으로 정리된 힙 구조를 Min-Heap이라고 함

PriorityQueue -> Min Heap 구조를 바탕으로 함

 

poll() : 큐에서 가장 상단에 있는 것을 출력, 우선순위 큐에서는 우선순위로 되어있는 것부터 출력

peek() : 가장 상단에 있는 것 출력(여기서는 부모노드 출력)

 

public class Practice1 {
    public static int solution1(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 일단 우선순위 큐 생성

        for (int num : nums){
            pq.offer(num); // 숫자 배열 전체를 큐에 추가

            if(pq.size() > k){
                pq.poll();
            }
        }
        return pq.peek();
    }

    public static void main(String[] args) {
        // Test code
        int[] nums = {3, 1, 2, 7, 6, 4};
        System.out.println(solution1(nums, 2));
        System.out.println(solution2(nums, 2));
        System.out.println();

        nums = new int[]{1, 3, 7, 4, 2, 8, 9};
        System.out.println(solution1(nums, 7));
        System.out.println(solution2(nums, 7));
    }

예제처럼 {3, 1, 2, 7, 6, 4}라면 풀이 방식

 

 

방법2. sort 정렬 알고리즘

public static int solution2(int[] nums, int k) {
    Arrays.sort(nums);
    return nums[nums.length - k];
}

 

 

연습문제2. 무게가 무거운 순으로 돌끼리 충돌시킨 후에 남은 것 출력하기

방법1. 무게를 우선순위로 둔 우선순위 큐 자료구조를 통하여 출력하기

무게를 바탕으로 우선순위 큐를 작성

public class Practice2 {
    public static void solution(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int stone: stones){
            pq.offer(stone);
        }

        while (pq.size() > 1){
            int stone1 = pq.poll();
            int stone2 = pq.poll();
            int diff = Math.abs(stone1 - stone2);

            if (diff !=0){
                pq.offer(diff);
            }
        }
        System.out.println(pq.poll());
    }

 

 

 

 

연습문제3. 빈도수를 카운트 한 뒤에, 빈도수가 높은 순으로

 

연습문제4. 문자열 연속적으로 동일 문자 없이 재배치

방법. 빈도수를 센 다음에 우선순위 큐로 넣고 안 겹치게 배치를 해줘야함

우선순위 큐를 이용한 정렬이 가능