[백준 - 1715] 카드 정렬하기

이 문제 덕분에 우선순위 큐를 처음으로 사용하게 되었다.

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

int main()
{
	int N;
	cin >> N;

	priority_queue<int, vector<int>,greater<int>> list;
	for (int i = 0; i < N; ++i)
	{
		int temp = 0;
		cin >> temp;
		list.push(temp);
	}

	int result = 0;
	while (list.size() != 1)
	{
		int cardA = list.top();
		list.pop();
		int cardB = list.top();
		list.pop();
		list.push(cardA + cardB);
		result += cardA + cardB;
	}

	cout << result;

	return 0;
}

 

근데 최근에 삽입정렬을 보아서 문득 든 생각이였는데

어차피 최소값 두개를 합쳐서 그 값을 다시 넣는걸 반복하는거면

처음에 값을 받고 퀵정렬로 정렬 후에 연산을 하면 거의 정렬 된 상태이니까 삽입정렬도 메리트 있지 않을까? 생각했다.

 

결과는 정답은 나오지만 시간초과였다

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

void Swiching(int & a, int & b)
{
	int temp = a;
	a = b;
	b = temp;
}

void InsertionSort(vector<int> & numList, int size)
{
	for (int i = 1; i < size; ++i)
	{
		for (int j = i; 0 < j; --j)
		{
			if (numList[j] < numList[j - 1])
			{
				Swiching(numList[j - 1], numList[j]);
			}
		}
	}
}

int main()
{
	int N;
	cin >> N;

	vector<int> list;
	for (int i = 0; i < N; ++i)
	{
		list.push_back(0);
		cin >> list[i];
	}

	sort(list.begin(), list.end());

	int result = 0;
	for (int i = 0; i < N - 1; ++i)
	{
		list[i + 1] = list[i] + list[i + 1];
		result += list[i + 1];
		InsertionSort(list, N);
	}

	cout << result;

	return 0;
}

 

이렇게 업데이트 되는 배열속에서 최대, 최소값을 계속 확인해야하는 상황이라면

일단은 우선순위 큐를 사용하는게 빠르다고 느꼈다 =~=