1927번 - 최소 힙

출처: 백준 알고리즘

주소: www.acmicpc.net/problem/1927  

1927번: 최소 힙

1927번 - 최소 힙

문제 요약:

 (1) 최소 힙 클래스 생성

     => 힙의 최대 크기(N): 100000, 힙에 저장되는 자연수의 범위: 1 ~ 2³¹ - 1

 (2) x값이 0이면 힙에서 가장 작은 값을 출력하고, 그 값을 힙에서 제거

 (3) x값이 자연수이면 힙에 삽입

 

문제 해결:

 A. 최소 힙 클래스 정의

 B. 최소 힙 클래스 내의 삽입 함수 생성

 C. 최소 힙 클래스 내의 최소 값 삭제 함수 생성

 

참고 사이트:

 이전에 최대 힙을 구현하기 위해, C언어 방식인 struct로 HeapType을 설정하고 함수를 구현하여 계산하였다.

trying-ce-student.tistory.com/14

11279번 - 최대 힙

알고리즘:

 

   A. 최소 힙 클래스 정의(HeapClass)

    1. 클래스 변수(private)

     - heap을 저장하는 배열 heap 생성(heap)

       => 배열의 크기: 100001(인덱스 1부터 저장), 타입: long long int

     - heap size를 저장하는 변수 생성(heap_size)

       => 타입: int

 

    2. 클래스 함수(public)

     - HeapClass 생성자

       => heap_size를 0으로 초기화

     - 입력받은 값(x)을 힙에 저장하는 함수(InputX)

       => 반환값 없음(void), 입력값(x)의 타입: long long int

     - 최소 값을 제거하고 출력하는 함수(DeleteX)

       => 반환값 없음(void), 입력값 없음

     - heap_size를 반환하는 함수(HeapSize)

       => 반환값: int, 입력값 없음

 

    이후 방식은 이전 사이트와 동일

 

소스 코드:

#include <iostream>
 
#define MAX_VEC_LEN 100001
 
class HeapClass {
private:
    long long int heap[MAX_VEC_LEN];
    int heap_size;
 
public:
    HeapClass();
    void InputX(long long int x);
    void DeleteX();
    int HeapSize();
};
 
HeapClass::HeapClass() {
    heap_size = 0;
}
 
void HeapClass::InputX(long long int x) {
    // heap_size을 1 증가
    int heap_input_idx = ++heap_size;
 
    // 1. 현재 idx가 1보다 큰 경우
    // 2. 입력 값이 그 위치의 부모값보다 작은 경우
    while ((heap_input_idx != 1) && (x < heap[heap_input_idx / 2])) {
        // 현재 idx 위치에 부모 값을 대입
        heap[heap_input_idx] = heap[heap_input_idx / 2];
 
        // 현재 idx 갱신
        heap_input_idx /= 2;
    }
 
    // 새로운 값을 해당 위치에 대입
    heap[heap_input_idx] = x;
    
}
 
void HeapClass::DeleteX() {
    // child_idx와 parent_idx 설정
    // 삭제할 값과 대체할 값 저장, heap_size 1 감소
    int child_idx, parent_idx;
    long long int del_x = heap[1];
    long long int repl_x = heap[(heap_size)--];
 
    parent_idx = 1;
    child_idx = 2;
 
    // 자식 노드의 idx가 heap_size보다 작은 경우 반복
    while (child_idx <= heap_size) {
        // 자식 노드 중에서 더 작은 값 저장
        if ((child_idx < heap_size) && (heap[child_idx] > heap[child_idx + 1])) {
            child_idx++;
        }
        // 현재 노드보다 마지막 값이 작은 경우
        if (repl_x <= heap[child_idx]) {
            break;
        }
 
        heap[parent_idx] = heap[child_idx];
 
        // 현재 노드가 부모 노드로 설정
        parent_idx = child_idx;
        // 현재 노드의 왼쪽 자식 노드로 이동
        child_idx *= 2;
    }
 
    heap[parent_idx] = repl_x;
 
    printf("%lld\n", del_x);
}
 
 
int HeapClass::HeapSize() {
    return heap_size;
}
 
int main() {
    // 변수 선언
    int n;
    long long int x;
    HeapClass min_heap;
 
    // 초기화 및 입력
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &x);
 
        // x 값이 0인 경우 (최소값 출력)
        if (x == 0) {
            // min_heap이 비어있는 경우에는 0을 출력
            if (min_heap.HeapSize() == 0) {
                printf("%d\n", 0);
            }
            else {
                min_heap.DeleteX();
            }
        }
        // x 값이 0이 아닌 경우
        // min_heap에 x 값을 대입
        else {
            min_heap.InputX(x);
        }
    }
    return 0;
}

 

한줄평:

 -> C++에서 클래스로 구현하는 게 더욱 편하다.