SWEA - 힙 (STL 사용 X)

문제

https://swexpertacademy.com/main/talk/codeBattle/problemDetail.do?contestProbId=AV-Tj7ya3jYDFAXr&categoryId=AYIPD136YD8DFATO&categoryType=BATTLE&battleMainPageIndex=1 

SW Expert Academy

힙을 구현한 후, 1과 함께 어떤 숫자가 입력되면 그 수를 힙에 추가하고,

2가 입력되면 루트 노드를 출력하고 삭제한다.

풀이

처음에 10^5를 바보같이 10000로 생각해서 계속 런타임 에러가 났다..ㅋ

배열 크기는 여유있게 100005 정도로 잡아두고,

배열을 이용해서 heap을 구현했다.

유의해야할 점은, heap이 비어있을 때, 계속해서 last를 감소시키면 안 된다.

heap이 비어있다면(last가 1이라면) -1을 출력하고 continue 한다.

 

코드

#include<iostream>
#include<cstring>
using namespace std;

int arr[100005];

void myswap(int a, int b)
{
    int tmp = arr[b];
    arr[b]=arr[a];
    arr[a]=tmp;
}

void findlocation(int cur, int last)
{
    int leftidx = cur*2;
    int rightidx = leftidx+1;
    int biggest = cur;
    
    if(leftidx<=last && arr[leftidx]>arr[cur]) biggest = leftidx;
    if(rightidx<=last && arr[rightidx]>arr[biggest]) biggest = rightidx;
    if(biggest==cur) return;
    else
    {
        myswap(cur,biggest);
        findlocation(biggest,last);
    }
}

void heapify(int last)
{
    int cur_idx = last/2;
    while(cur_idx>=1)
    {
        findlocation(cur_idx,last);
        cur_idx--;
    }
}

void addToHeap(int v, int last)
{
    int cur = last+1;
    int parent = cur/2;
    arr[cur] = v;
    while(1)
    {
     	if(arr[parent]>arr[cur]) return;
        else
        {
         	myswap(parent, cur);
            cur=parent;
            parent=cur/2;
            if(parent<1) return;
        }
    }
}

int removeRoot(int last)
{
    int ret = arr[1];
    arr[1]=arr[last];
    findlocation(1,last-1);
    return ret;
}

int main(int argc, char** argv)
{
	int test_case;
	int T;
    scanf("%d",&T);
	for(test_case = 1; test_case <= T; ++test_case)
	{
        printf("#%d ",test_case);
        memset(arr,0,sizeof(arr));
        int n;
        scanf("%d",&n);
        int last=1;
        for(int i=0; i<n; i++)
        {
            int a;
            scanf("%d",&a);
            if(a==1)
            {
             	int b;
                scanf("%d",&b);
                addToHeap(b,last);
                last++;
            }
            else
            {
                if(last==1) 
                {
                    printf("-1 ");
                    continue;
                }
                printf("%d ",removeRoot(last));
                last--;
            }
        }
        printf("\n");
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}