BOJ 백준 1715 : 카드 정렬하기

시작하면서

이번 문제는 힙(heap) 카테고리 문제이다. 저번 주차에 하지 못한 우선 순위 큐 관련 문제를 풀기 위해서 해당 문제를 골랐다.

BOJ 1715 - 카드 정렬하기

​

개념

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조로서 다음과 같은 힙 속성을 만족한다.

• A가 B의 부모노드이면, A의 키값과 B의 키값 사이에는 대소관계가 성립한다.
• 힙에는 두 가지 종류가 있다. 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙을 ‘최대 힙’, 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙을 ‘최소 힙’이라고 부른다.
• 키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는다.
• 각 노드의 자식노드의 최대개수는 힙의 종류에 따라 다르지만, 대부분의 경우는 자식노드의 개수가 최대 2개인 이진 힙(binary heap)을 사용한다.
• 힙에서는 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 뿌리노드에 오게 되는 특징이 있으며, 이를 응용하면 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.
• 힙 (삽입의)시간복잡도는 O(logn)이다. 그 이유는 이진트리의 속성에서 힙트리의 높이 h = log(n+1) 이므로, O(logn)이다.

​

문제 이해

문제를 읽어보자. 먼저 이 문제에서 나오는 변수는 총 2가지이다.

• N : 숫자 카드 묶음의 개수

• A : 숫자 카드 묶음들

  이 변수를 가지고 답을 출력해야 한다.

​

문제 아이디어

해당 문제는 카드 묶음을 합칠 때마다 비교 횟수를 최소로 만들어야 한다. 이를 위해서는 매번 카드 묶음을 합칠 때 가장 작은 묶음 2개를 꺼내서 비교해야 한다.

1. 카드 묶음의 값들을 받아서 “오름차순 우선순위 큐”에 넣어준다.
2. top에서 2개의 값을 꺼내서 카드 묶음을 더해준다. 그리고 비교한 값을 세준다.
3. 더해준 묶음을 다시 “오름차순 우선순위 큐”에 넣어준다.
4. 위 작업들을 “오름차순 우선순위 큐”에 값이 1개가 남을 때까지 진행한다. (카드 묶음이 1개가 될 때까지)

​

해결

#include <iostream>
#include <queue>

using namespace std;

void Input();
void SolveProblem();
void PrintAnswer();

int N, result;
priority_queue<int, vector<int>, greater<int> > pq;

int main()
{
	// sync off
	ios::sync_with_stdio(false);
	cin.tie(0);

	Input();
	SolveProblem();
	PrintAnswer();
}

void Input()
{
	int value;

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> value;
		pq.push(value);
	}
}

void SolveProblem()
{
	while (pq.empty() == false && pq.size() > 1)
	{
		int num0 = pq.top(); pq.pop();
		int num1 = pq.top(); pq.pop();
		int sum = num0 + num1;
		result += sum;
		pq.push(sum);
	}
}

void PrintAnswer()
{
	cout << result;
}

처음에 문제를 풀 때에는 sum을 다시 pq에 넣지 않는 실수를 했었다. 음.. 그거 말고는 따로 어려운 부분은 없었던, 우선 순위 큐를 사용하면 쉽게 풀 수 있는 문제였다.

​

마치며

저번 주차에 우선 순위 큐 문제를 제대로 풀지 못해 아쉬워서 한 주 더 진행했는데, 생각보다 기초 문제여서 아쉽긴 하다. 하지만 힙에 대한 개념 공부를 다시 했으니 만족한다.