[리마인드] 힙(우선순위 큐) 코딩테스트 문제

오늘의 학습키워드

힙
우선순위 큐

 

다시풀기 문제

1. 프로그래머스 Level 2 - 더 맵게

• https://school.programmers.co.kr/learn/courses/30/lessons/42626
• Github 풀이

프로그래머스

Algorithm-Practice/프로그래머스/2/42626. 더 맵게 at main · dev-jinius/Algorithm-Practice

 

2. LeetCode Medium -  1845. Seat Reservation Manager

• https://leetcode.com/problems/seat-reservation-manager/description
• Github 풀이

Algorithm-Practice/LeetCode/1845-seat-reservation-manager/1845-seat-reservation-manager.java at main · dev-jinius/Algorithm-Pra

 

 

 

Heap (힙)

 

 

1. 힙은 이진트리 기반의 자료구조

2. 최소 힙은 루트 노드에 최솟값, 최대 힙은 루트 노드에 최댓값이 저장된다.

3. 삽입, 삭제 연산의 시간 복잡도는 O(logN)으로 매우 효율적이다.

4. 최솟값/최댓값 조회 연산의 시간 복잡도는 O(1)로 매우 빠르다.

 

회고

1. 프로그래머스 Level 2 - 더 맵게

어디까지 생각해봤나?

• 앞선 큐 문제처럼 2개 스코빌 지수를 묶는건데 정렬순으로 앞에서 2개씩 묶음이 필요하다는 점
• 계속해서 새로운 데이터를 정렬시켜야 한다는 점
• 자동 정렬되는 자료구조인 PriorityQueue를 생각했다.

핵심

• 데이터에서 최솟값을 반복적으로 가져오면서, 우선순위대로 처리해야 하므로 힙 자료구조가 적합하다.
• 가장 작은 두 값을 효율적으로 찾아 조합하는 것!

 

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int scov : scoville) 
            pq.add(scov);
       
        int count = 0;
        int current = -1;
        
        while (pq.peek() < K) {
            if (pq.size() == 1) return -1;
            
            current = pq.poll();
            current = current + (pq.poll()*2);
            pq.add(current);
            count++;
        }
        
        return count;
    }
}

 

 

2. LeetCode Medium -  1845. Seat Reservation Manager

어디까지 생각해봤나?

• 좌석을 예약하면, 숫자 순서대로 예약이 되니까 우선순위 큐를 사용하면 좋겠다고 생각했다.

핵심

• 최소 힙
• 가장 작은 비어있는 좌석 번호를 빠르게 조회하기

 

import java.util.Queue;
import java.util.PriorityQueue;

class SeatManager {
    Queue<Integer> seats;

    public SeatManager(int n) {
        seats = new PriorityQueue<>();
        for (int i = 1; i <= n; i++)
            seats.offer(i);
    }
    
    public int reserve() {
        return seats.poll();
    }
    
    public void unreserve(int seatNumber) {
        seats.offer(seatNumber);
    }
}