c언어 1715번 카드정렬하기

#include <stdio.h>
#define MAX_SIZE 100000 //우선순위 큐를 배열을 이용한 최소힙으로 구현했기에, 미리 배열의 크기를 지정해 주었다.
//여기서 힙정렬의 시작을 0으로 했습니다.
void swap(int *x, int *y) { //swap 함수
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

typedef struct PriorityQueue { //최소힙으로 만든 우선순위 큐
	int heap[MAX_SIZE]; //힙을 이룰 배열
	int cnt; //우선순위 큐에 있는 요소들의 개수
}PriorityQueue;

void push(PriorityQueue *q, int data) { //큐에 집어넣기 -> 집어넣으면 최소힙으로 정렬된다.
	q->heap[q->cnt] = data; //새로운 노드에 요소로 들어온 데이터를 저장 (새로운 노드의 번호는 가장 마지막이다)
	
	int child = q->cnt; //이번에 생긴 노드의 번호
	int parent = 0; //부모의 번호를 담을 변수
	if(child) parent = (child-1)/2; //원래 큐에 노드가 1개 이상이라면 -> 이번에 생긴 노드의 부모가 존재한다는 의미 -> 부모노드의 번호를 저장
	//아래에서 root쪽으로 최소힙정렬
	while(child && q->heap[child] < q->heap[parent]) {//child이 0이되면 이는 root라는 의미이므로, 더이상 부모노드가 존재하지 않으므로 반복문 종료, 최소힙이므로, 자식노드가 부모노드보다 크면 swap되지 않으니 반복문 종료
		swap(&q->heap[child], &q->heap[parent]); //swap
		child = parent; //swap했으니, 자식노드를 부모노드로
		parent = (parent-1)/2; //부모노드는 부모의 부모노드로
	}
	q->cnt++; //우선순위 큐의 노드의 개수가 늘어났으니 1 증가
}

int pop(PriorityQueue *q) { //우선순위 큐의 root을 return
	int res = q->heap[0]; //root값을 저장
	q->cnt--; //root값을 제거 했으니 개수 1 감소
	q->heap[0] = q->heap[q->cnt]; //마지막 노드를 root에 대입, 물론 굳이 마지막노드가 있는 배열을 0으로 초기화 하지는 않았다.
	
	int parent = 0, tmp=0; //부모노드는 0
	int leftChild = 1; //그 아래 왼쪽 자식은 1
	int rightChild = 2; //오른쪽 자식은 2
	/root에서 아래로 최소힙정렬
	while(leftChild < q->cnt) { //왼쪽 자식의 번호가 큐의 전체개수보다 같거나 크면, (index가 0부터이므로) 큐의 개수를 초과한 것이니, 없는 노드이다! 고로 반복문을 종료한다.
		if(q->heap[tmp] > q->heap[leftChild]) tmp = leftChild; //부모노드보다 더 작으면, 일단 tmp라는 변수에 자식노드의 번호를 저장
		if(q->heap[tmp] > q->heap[rightChild] && rightChild < q->cnt) tmp = rightChild; //왼쪽자식노드, 그리고 부모노드보다 작다면 오른쪽 자식노드의 번호를 tmp에 저장
		if(parent == tmp) break; //만약 자식 보다 부모노가 더 작다면 더이상 힙정렬을 할 필요가 없다.
		else { //자식이 더 작으면 swap하고, 한 층 위로 올라간다.
			swap(&q->heap[parent], &q->heap[tmp]);
			parent = tmp;
			leftChild = parent*2+1;
			rightChild = leftChild+1;
		}
	}
	return res; //처음에 대입한 root값을 반환
}

int main(void) 
{
	PriorityQueue queue; //우선순위 큐 생성
	queue.cnt = 0; //우선순위 큐의 개수 초기화 (처음 만들어졌으니 노드 개수는 0)
	
	int n;
	int sum = 0;
	scanf("%d", &n);
	
	int tmp;
	
	for(int i=0; i<n; i++) { //데이터 입력
		scanf("%d", &tmp);
		push(&queue, tmp);
	}
	
	while(n>=2) {
		tmp = pop(&queue)+pop(&queue); //가장 작은 두개의 뭉치를 더함
		sum += tmp; //이를 전체 세는 수에 저장함
		push(&queue, tmp); //또한 합친 더미를 다시 우선순위 큐에 넣음
		n--;
	} printf("%d", sum);
	return 0;
}

 

 

풀이 : 우선순위 큐(최소힙)

 

10 20 30 40 50 60 의 크기를 가진 더미가 있을 때

최대한 효율적으로 더미들을 합치기 위해선, 크기가 적은 것들로 많이 합쳐야 한다.

 

그러므로

(10+60) + (20+50) + (30+40) 이런식도 아니고

(10+20) + (30+40) + (50+60) 이런것도 아니다.

 

가장 크기가 작은 두 더미를 합친 다음, 여기서 나온 새로 만든 더미와

기존의 더미들의 크기를 비교한 다음 여기서 또 가장 작은 두 더미를 골라 합치고...

이 과정을 반복해야 가장 효율적으로 더미들을 합칠 수 있게 된다.

 

1. 크기를 지정한 배열을 이용하여 최소힙의 구조를 지닌 우선순위 큐를 구현한다.

2. 데이터들을 입력 받고 우선순위 큐에다가 집어넣는다.

3. 가장 앞에있는 값 두개를 꺼낸 뒤 합친다. 그리고 다시 집어넣는다

4. 3.을 우선순위 큐에 더미가 한개만 남을때까지 계속한다.

5. 더미들을 합칠때 합치는 더미들의 개수들을 누적한 값을 출력한다.