[프로그래머스] 튜플

✔️ 문제 링크

https://programmers.co.kr/learn/courses/30/lessons/64065

프로그래머스

---

✔️ 풀이

- 튜플을 구하려면, 우선 주어진 집합을 크기 순으로 오름차순 정렬한다.

- "{{1,2,3},{2,1},{1,2,4,3},{2}}" -- > "{{2},{2,1},{1,2,3},{1,2,4,3}}"

- 원소 수가 K인 집합과 K – 1인 집합의 차집합(단, K > 1)의 원소가 튜플의 K번째 원소를 나타낸다.

- 위와 같은 방법을 그대로 구현하면 된다.

---

✔️ 문제 회고

- 문제를 풀기 위해서는 "원소 수가 K인 집합과 K – 1인 집합의 차집합(단, K > 1)의 원소가 튜플의 K번째 원소를 나타낸다." 라는 규칙을 찾아내야한다. 

- 집합을 정렬하기 위해 주어진 문자열을 적절히 파싱하여 각 집합을 vector로 만들었다. 

- 집합의 크기 순으로 정렬하기 위해  piar<크기, 벡터>를 사용했다.

- 처음엔 규칙을 찾지 못해 못풀었는데, 나중에 다시푸니 풀렸다. 쉬운 문제였다. 규칙만 찾는다면, 상당히 쉽게 풀 수 있는 문제다. 

---

👨🏻‍💻 소스 코드 1 

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

vector<int> solution(string s) {

	vector<int> answer;

	vector<pair<int, vector<int>>> arr;
	bool start = false;
	vector<int> element;
	int num = 0;
	
	for (int i = 1; i < s.size() - 1; i++) { //문자열 전처리
		if (s[i] == ',' && s[i + 1] == '{') {
			s.erase(s.begin() + i);
		}
	}
	
	for (int i = 1; i < s.size() - 1; i++) { // 각 집합을 파싱하여 vector로 만든다. 
		if (s[i] == '{') continue;

		if (isdigit(s[i]))
			num = num * 10 + s[i]-'0';

		if (s[i] == ',' || s[i] == '}') {
			element.push_back(num);
			num = 0;
		}

		if (s[i] == '}') {
			arr.push_back({ element.size(), element });
			element.clear();
		}
	}

	sort(arr.begin(), arr.end()); // 집합의 크기순으로 정렬한다. 

	bool check[100001] = { false };

	for (int i = 0; i < arr.size(); i++) { // 차집합을 구한다. 
		for (int j = 0; j < arr[i].second.size(); j++) {
			int num = arr[i].second[j];
			if (!check[num]) {
				check[num] = true;
				answer.push_back(num);
			}
		}
	}

	return answer;
}