문제

문자열 파싱하다가 넘 귀찮고 헷갈렸는데, 생각해보니 튜플 (a1, a2, a3, ..., an)을 표현한 집합 [[a1], [a1, a2], [a1, a2, a3], [a1, a2, a3, a4], ... [a1, a2, a3, a4, ..., an]]에서 각 원소의 등장 빈도는 다음과 같다:

a1: n
a2: n-1
a3: n-2
...
an: 1

그래서 그냥 모든 원소에 대해 등장 횟수를 계산한 다음 등장 횟수에 대해 내림차순으로 정렬한 것이 튜플이다.

#include <string>
#include <vector>
#include <unordered_map> 
#include <algorithm> // sort
using namespace std;

bool cmp(pair<int, int> a, pair<int, int> b) {
	return a.second > b.second;
}

vector<int> solution(string s) {
	vector<int> answer;
	unordered_map<int, int> umap; // (원소, 빈도)

	int i, size = s.size();
	string tmp = "";

	for (i = 0; i < size; i++) {
		if (s[i] == '{' || s[i] == '}' || s[i] == ',') {
			if (tmp != "") {
				umap[stoi(tmp)]++;
				tmp = "";
			}
		}
		else tmp += s[i];
	}

	vector< pair<int, int> > v(umap.begin(), umap.end());
	sort(v.begin(), v.end(), cmp);

	for (i = 0; i < v.size(); i++) answer.push_back(v[i].first);

	return answer;
}