알고스팟: 문자열 합치기 (ID: STRJOIN)

[문제 링크]

algospot.com :: STRJOIN

---

간단한 그리디 알고리즘 문제였다.

항상 길이가 가장 짧은 두 문자열을 합치는 것이 최적해를 보장하기 때문에, 오름차순 정렬을 통해 길이가 가장 짧은 두 문자열을 합치도록 구현하였다.

 

삽입, 삭제 연산이 빈번할 때 유리한 list 컨테이너를 사용하였다. 두 문자열을 합칠 때마다 새로운 원소가 추가되기 때문에 오름차순 정렬을 수행해줬다.

 

또한 원소를 삽입할 때 자동으로 정렬되어 삽입되는 set 컨테이너를 사용해서 구현해보았는데, 원소 검색에 효율적인 set 컨테이너는 삽입 삭제 연산에 시간이 오래 걸린다는 단점이 있어 시간초과가 날수도 있겠다 생각했지만 통과되었다.

 

// 추가: 알고리즘 문제해결 전략에서는 priority_queue 를 사용하여 구현하였다. 우선순위큐는 원소를 자동으로 정렬해줄뿐더러 새 원소를 추가하는 작업을 log시간에 할 수 있기 때문에 가장 효율적이다.

---

<list 사용>

#include <iostream>
#include <list>
using namespace std;

list<int> str;

int Greedy(int n)
{
	if (n == 1)
		return str.front();

	int result = 0;
	while (--n)
	{
		str.sort();

		int join = 0;
		for (int i = 0; i < 2; i++)
		{
			join += str.front();
			str.pop_front();
		}
		result += join;
		str.push_back(join);
	}

	return result;
}

int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		int n;
		cin >> n;

		for (int i = 0; i < n; i++)
		{
			int len;
			cin >> len;
			str.push_back(len);
		}

		cout << Greedy(n) << endl;
		str.clear();
	}

	return 0;
}

<multiset 사용>

#include <iostream>
#include <set>
using namespace std;

multiset<int> str;

int Greedy(int n)
{
	if (n == 1)
		return *str.begin();

	int result = 0;
	while (--n)
	{
		int join = 0;
		for (int i = 0; i < 2; i++)
		{
			join += *str.begin();
			str.erase(str.begin());
		}
		result += join;
		str.insert(join);
	}

	return result;
}

int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		int n;
		cin >> n;

		for (int i = 0; i < n; i++)
		{
			int len;
			cin >> len;
			str.insert(len);
		}

		cout << Greedy(n) << endl;
		str.clear();
	}

	return 0;
}

<priority_queue 사용>

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


priority_queue<int, vector<int>, greater<int>> str;

int Greedy(int n)
{
	int result = 0;

	if (n == 1)
	{
		result = str.top();
		str.pop();
		return result;
	}

	while (--n)
	{
		int join = 0;
		for (int i = 0; i < 2; i++)
		{
			join += str.top();
			str.pop();
		}
		result += join;
		str.push(join);
	}

	str.pop();
	return result;
}

int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		int n;
		cin >> n;

		for (int i = 0; i < n; i++)
		{
			int len;
			cin >> len;
			str.push(len);
		}

		cout << Greedy(n) << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 109 day