[HackerRank] Jesse and Cookies / Insertion Sort - Part 1

# Jesse and Cookies (Heap)

[문제]

 

[코드]

void insert_heap(int item, int *heap, int *n)
{
    int i;
    i = ++(*n);
    while((i != 1) && item < heap[i/2])
    {
        heap[i] = heap[i/2];
        i /= 2;
    }
    heap[i] = item; 
}

int delete_heap(int *heap, int *n)
{
    int child, item, temp;
    
    item = heap[1];
    temp = heap[(*n)--];
    child = 2;
    while(child <= *n)
    {
        if((child != *n) && (heap[child] > heap[child+1]))
            child++;
        if(temp <= heap[child]) break;
        heap[child/2] = heap[child];
        child *=2;
    }
    heap[child/2] = temp;
    return item;
}

void make_heap(int *heap, int root, int n)
{
    int child, temp;
    temp = heap[root];
    child = root*2;
    
    while(child <=n)
    {
        if((child != n) && (heap[child] > heap[child+1]))
            child++;
        if(temp <= heap[child]) break;
        else {
            heap[child/2] = heap[child];
            child*=2;
        }
    }
    heap[child/2]=temp;
}

int cookies(int k, int A_count, int* A) {
    int num1, num2, combine, result = 0;
    int *B = (int*)malloc(sizeof(int)*(A_count+1));
    
    for(int i = 1; i <= A_count; i++)
        B[i] = A[i-1];
    for(int i = A_count/2; i>0; i--)
        make_heap(B, i, A_count);
        
    if(B[1] >= k) return result;
        
    while(A_count > 1)
    {
        result++;
        num1 = delete_heap(B, &A_count);
        num2 = delete_heap(B, &A_count);
        combine = num1 + num2 * 2; 
        insert_heap(combine, B, &A_count);
        if(B[1] >= k)
            return result;
    }   
    return -1;
}

 

[코드설명]

우선순위 큐를 사용해서 해결하는 문제다. 필자는 최소 힙으로 우선순위 큐를 구현했다.

힙에서 가장 작은 sweetness 2개를 추출해야 하기 때문에 최소 힙으로 구현했다.

먼저 힙을 구현하기 위해 배열에서 0번째 인덱스를 제외했다.

B라는 배열을 동적할당 하고, sweetness를 인덱스 1부터 다시 저장했다.

그리고 최소 힙을 구현하기 위해 i/2부터 1번째 인덱스에 대해 make_heap을 실행했다. make_heap은 루트에서 부터 단말노드까지 더 작은 값을 부모로 올려주는 함수다.

힙에서 루트의 value가 k보다 크거나 같다면 모든 sweetness가 k보다 크거나 같다는 뜻이므로 combine 과정을 거치지 않아도 된다.

루트의 value가 k보다 작다면 combine 과정을 거쳐야 한다. 이때 combine을 해야 하므로 heap의 크기는 1보다 커야 한다.

combine할 때마다 result 값은 1 증가되고, delete_heap과 insert_heap을 통해 combine된 값을 최소 힙에 추가한다. (insert_heap과 delete_heap은 각각의 연산 후에 최소 힙 상태를 유지한다.)

마지막엔 루트의 value가 k이상인지 확인하고 참이면 result를 반환한다.

반대로 위 코드의 모든 조건에 부합하지 않을 시 -1을 반환한다.

 

 

[채점 결과]

 

 

 

 

 

# Insertion Sort - Part 1 (Sorting)

[문제]

 

[코드]

void print_arr(int *arr, int n)
{
    for(int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

void insertionSort1(int n, int arr_count, int* arr) {
    int i, temp = arr[n-1];
    
    for(i = n-2; i >= 0; i--)
    {   
        if(temp < arr[i])
            arr[i+1] = arr[i];
        else
            break;
        print_arr(arr, n);
    }
    arr[i+1]=temp;
    print_arr(arr, n);
}

 

[코드설명]

이번 문제는 삽입정렬 과정을 print하는 문제다.

arr 배열의 마지막 원소를 temp에 저장한다.

마지막 원소 바로 앞의 원소부터 시작해서 첫 번째 원소까지 temp의 값과 비교한다.

만약 temp가 arr[i]보다 작다면 arr[i]의 값을 바로 다음 인덱스에 복사한다.

반대로 temp가 arr[i]보다 크거나 같다면 원소를 swap할 필요가 없으므로 반복문을 중단하고 현재 위치(arr[i+1])에 temp를 저장한다.

원소를 swap(원소의 복사)할 때와 temp의 값을 저장할 때 배열의 상태를 print한다.

 

[채점 결과]