BOJ - 카드 정렬(1715)

최대 힙(MaxHeap)을 연습하기 위해 풀어본 문제입니다. 문제를 풀기 위해서는 가지고 있는 카드 묶음 중 가장 작은 두 묶음을 찾아서 더해주어야 했기 때문에 최소 힙(MinHeap)을 사용했습니다. 가장 작은 묶음 두 개를 꺼내서 더해준 후 다시 최소 힙에 넣어줍니다. 힙 안에 한 개만 남을 때까지 반복합니다. 힙만 구현하면 메인 함수는 매우 간단합니다.

최소 힙(MinHeap)

// 초기화
int minHeap[200005];
int lastIdx = 0;

// 자식 노드 Index 
int getLeftChild(int idx) {
	return idx * 2;
}

int getRightChild(int idx) {
	return idx * 2 + 1;
}

// 부모 노드 Index 
int getParent(int idx) {
	return idx / 2;
}

// 교환하는 함수
void swap(int idx1, int idx2, int* arr) {
	int tmp = arr[idx1];
	arr[idx1] = arr[idx2];
	arr[idx2] = tmp;
}

// dequeue 함수
int dequeue() {

	if (lastIdx == 0) return -1;

	int maxVal = minHeap[1];
	minHeap[1] = minHeap[lastIdx];
	minHeap[lastIdx] = 0;
	lastIdx--;

	int curIdx = 1;
	while (true) {
		int left = getLeftChild(curIdx);
		int right = getRightChild(curIdx);

		int curVal = minHeap[curIdx];

		int leftVal = minHeap[left];
		int rightVal = minHeap[right];

		int nextIdx;
		int nextVal;

		// 자식 노드가 없는 경우
		if (lastIdx < left) {
			break;

		// 왼쪽 자식 노드만 있는 경우 
		} else if (lastIdx == left) {
			nextIdx = left;
			nextVal = minHeap[nextIdx];

		// 둘 다 있는 경우 비교
		} else if (lastIdx >= right) {
			nextIdx = leftVal < rightVal ? left : right;
			nextVal = minHeap[nextIdx];
		}

		if (curVal > nextVal) {
			swap(curIdx, nextIdx, minHeap);
			curIdx = nextIdx;
		} else {
			break;
		}
	}

	return maxVal;
}

// enqueue 함수
void enqueue(int val) {
	lastIdx++;
	minHeap[lastIdx] = val;

	int curIdx = lastIdx;
	while (true) {
		if (curIdx == 1) break;

		int nextIdx = getParent(curIdx);

		int curVal = minHeap[curIdx];
		int nextVal = minHeap[nextIdx];

		if (curVal < nextVal) {
			swap(curIdx, nextIdx, minHeap);
			curIdx = nextIdx;
		} else {
			break;
		}
	}
}

메인 함수

#include <stdio.h>

int main() {

	int N;
	scanf("%d", &N);

	int ans = 0;

	// enqueue
	while (N--) {
		int val;
		scanf("%d", &val);
		enqueue(val);
	}

	// 비교 횟수 계산
	while (lastIdx > 1) {
		int val1 = dequeue();
		int val2 = dequeue();
		
		ans += (val1 + val2);

		enqueue(val1 + val2);
	}

	printf("%d", ans);

}