[Binary min Heap(c++)] BOJ 15942 Thinking heap

문제

 

입력

첫 번째 줄에 자연수 N(1 ≤ N ≤ 200,000)이 주어진다. 두 번째 줄에 자연수 k와 p(1 ≤ k, p ≤ N)가 공백으로 구분되어 주어진다.

 

출력

자연수 k가 heap 배열의 p번째에 위치하도록 하는 삽입 순서가 존재한다면 i번째 줄에 i번째로 삽입할 수를 출력한다. 가능한 삽입 순서가 여러 가지라면 그중 아무거나 하나를 출력해도 된다. 만약 그렇게 만드는 삽입 순서가 존재하지 않는다면 첫 번째 줄에 -1을 출력한다.

 

풀이 방법

자료 구조

문제에 나와있는 것 처럼 1based의 1차원 배열을 통해 구현하면 된다.

 

heap[p] = k 임을 출력해야하므로 heap[p] = k를 넣고 다음 단계로 나아가면 된다. 그 다음 단계를 살펴 보자.

 

1.  k의 부모(조상)은 k보다 작은 수여야하고 자손은 k보다 큰 수여야 한다.

그러므로 k의 부모에는 차례대로 k-1부터 1까지 넣어줘야하고, 자식들에게는 k+1부터 N까지 넣어주면 된다.

 

만일, 조상 중에 0보다 작거나 같은 노드가 있거나, 자손 중 N보다 큰 노드가 있으면 문제에서 요구하는 heap을 만들지 못하는 것이므로 -1을 출력해주면된다.

 

2. 그렇게 구상한 배열에 채워지지 않은 곳이 있다면 채워준다. 이미 사용한 수를 제외하고 1부터 N까지의 수를 차례대로 넣어준다. 

 

이 과정에서 min heap의 조건을 만족하지 못하는 수가 있다면 그 조건을 만족할 때까지 원소를 바꿔준다.

 

3. 그 후 heap 배열을 출력한다.

 

코드

#include <iostream>
#include <algorithm>


using namespace std;
typedef long long ll;

int heap[200001]; //1-based -> 부모 idx 를 i 라고 하면 자식은 2i 와 2i+1 이다.
int n,k,p; //노드 수, heap[p]에 k가 와야한다.
int upnum, downnum; //k의 조상노드의 숫자 중 min, k의 자손 노드의 숫자 중 max
int heapnum=0; 

void dfs(int idx){ //k의 자손 채우기
    downnum++;
    if(downnum>n){ 
        cout<<-1;
        exit(0);
    }
    heap[idx]=downnum;
    if(idx*2 <=n) dfs(idx*2);
    if(idx*2+1 <= n) dfs(idx*2+1);
}
void flip(int idx){ //flip
    while(idx>1){
        if(heap[idx]<heap[idx/2]) swap(heap[idx], heap[idx/2]);
        idx/=2;
    }
}
void insert(int idx){ //k의 조상,자손 말고 나머지 채우기
    heapnum++;
    if(heapnum==upnum) heapnum=downnum+1;
    heap[idx]=heapnum;
    flip(idx); //조상에 나보다 더 큰 수 있으면 flip
    if(idx*2 <=n) insert(idx*2);
    if(idx*2+1 <=n) insert(idx*2+1);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>n>>k>>p;

    // k 있는곳의 부모, 자식 채우고, 사용한 숫자의 최소값upnum 최대값downnum 저장
    downnum=k-1;
    dfs(p); // heap[p]=k; 자손 채우기
    upnum=k;
    while(p/2>0){ // k의 조상 채우기
        p/=2, upnum--;
        heap[p]=upnum;
    }
    if(upnum<=0){ //예외처리
        cout<<-1;
        return 0;
    }

    // 배열순회하면서 안채워진곳(0인곳)을 1부터 heapnum++하며 채워준다.
    // 근데 그수가 최소값이나 최대값이면 다른수로. 그리고 필요시 flip처리
    for(int i=1; i<=n; i++){
        if(heap[i]) continue; //이미 채워져있으면 패스(k의 조상or자손인 경우)
        insert(i); //heap[i]와 그 노드의 자손들을 다 채워오자
    }

    //출력
    for(int i=1; i<=n; i++) cout<<heap[i]<<'\n';
    return 0;
}

 

참고

https://ezeun.tistory.com/101

[백준/C++] 15942번: Thinking Heap(G2)