백준 15903 c++ : 자료구조 multiset

vector와 sort를 매번 진행하는 경우 시간초과가 발생할 거 같아서, 정렬과 중복을 모두 지원하는 자료구조를 찾다가 multiset을 찾았다.
multiset은 set의 종류 중 하나로, set과 동일하게 자동정렬을 지원하며, 원소의 중복을 허용한다.
첫 시도에서는 int형으로 풀이하느라 오버으로 풀이하느라 오버플로우가 발생했고 long long으로 고쳐서 해결했다.

다른 사람들 풀이에서는 priority queue를 주로 사용했다. multiset에 비해서 현재 가장 작은 데이터 두개만 추출하는 과정이 덜 번거롭기 때문인거 같다.

사실 multiset과 priority queue를 활용하는 방식에서 차이는, multiset은 어떤원소든지 접근이 가능하고, priority queue는 정렬된 순서 중 가장 앞 원소만 차례대로 접근이 가능하다는 점 밖에 없는거 같다.

#include <iostream>
//#include <vector>
#include <set>

using namespace std;

void input_cards(int* n, int* m, /*vector<int>& cards*/ multiset<long long>& cards);
long long find_answer(int n, int m, /*vector<int>& cards*/ multiset<long long>& cards);

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	//vector<int> cards;
	multiset<long long> cards;
	
	input_cards(&n, &m, cards);
	cout << find_answer(n, m, cards) << "\n";

	return 0;
}

void input_cards(int* n, int* m, /*vector<int>& cards*/ multiset<long long> &cards) {
	int i, a_i;

	cin >> *n >> *m;
	for (i = 0; i < *n; i++) {
		cin >> a_i;
		//cards.push_back(a_i);
		cards.insert(a_i);
	}

	return;
}

long long find_answer(int n, int m, /*vector<int>& cards*/ multiset<long long> &cards) {

	/*
	* 카드 합체가 최소가 되게 하려면?
	1, 2, 3, 4, 5 이고, m이 3인 경우
	1, 2를 더해서 3으로 만들고 3, 3, 3, 4, 5
	3, 3을 더해서 6으로 만들고 6, 6, 3, 4, 5 -> 3, 4, 5, 6, 6
	3, 4를 더해서 7으로 만들고 7, 7, 5, 6, 6 

	4, 2, 3, 1이고, m이 2인 경우
	3, 3, 3, 4
	3, 4, 6, 6

	매 순간 정렬을 하면? -> 시간이 오래 걸릴 거 같은데
	*/

	long long temp_sum, A, B;
	long long sum = 0;
	int i;

	for (i = 0; i < m; i++) {
		auto first = cards.begin();
		A = *first;
		cards.erase(first);

		auto second = cards.begin();
		B = *second;
		cards.erase(second);

		cout << "A : " << A << " B : " << B << "\n";
		temp_sum = A + B;
		
		cards.insert(temp_sum);
		cards.insert(temp_sum);
	}

	for (long long card : cards) {
		sum += card;
	}

	return sum;
}