[프로그래머스] 튜플

[프로그래머스] 튜플

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

• 원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)의 경우
  {{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}} 로 표현 가능하다
  

• 예를 들어 튜플이 (2, 1, 3, 4)인 경우 이는
  {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}
  {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}
  {{2, 1, 3, 4}, {2}, {2, 1, 3}, {2, 1}}
  {{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}} 로 표현 가능하다

풀이 1

• 튜플을 집합으로 표현할 때 다음과 같은 규칙을 찾을 수 있다
  -> 튜플의 원소의 개수 N개만큼 집합이 만들어진다
  -> 튜플의 n(>=0)번째 원소는 N-n개의 집합에 포함된다

• 따라서 집합 표현 string s에서 각 숫자가 몇 번 반복되어 나타나는지 계산하면, 그 숫자가 튜플의 몇 번째 원소인지 알 수 있다
  -> 가장 많이 나타난 숫자가 튜플의 첫번째 원소이다
  (이때, 이 숫자가 나타난 횟수 = 총 집합의 개수 = 튜플에 포함된 원소의 수)
  -> 그 다음으로 많이 나타난 숫자는 두번째 원소이다

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

const int MAX_SIZE = 100005;

//해당 숫자가 집합 표현 string s에 몇 번 포함되었는지 저장
int cnt[MAX_SIZE] = { 0 };

bool cmp(int i, int j) {
	return j < i;
}

vector<int> solution(string s) {
	//가장 많이 나타난 숫자가 나타난 횟수 = 총 집합의 개수 = 튜플에 포함된 원소의 수
	int maxCnt = 0;

	string num = "";
	for (int i = 0; i < s.length(); ++i) {
		char ch = s[i];

		if (ch == '{' || ch == '"') continue;
		else if (ch == ',' || ch == '}') {
			if (num == "") continue;
			
			int pos = stoi(num);
			cnt[pos]++;
			if (maxCnt < cnt[pos]) maxCnt = cnt[pos];
			num = "";
		}
		else num += ch;
	}

	//maxCnt개의 원소를 가진 튜플 0으로 초기화
	vector<int> answer(maxCnt, 0);
    
	for (int i = 0; i < MAX_SIZE; ++i) {
		if (cnt[i] == 0) continue;
        
        //튜플의 n(>=0)번째 원소는 N-n개의 집합에 포함된다
        //m개의 집합에 포함된 원소는 튜플의 N-m번째 원소이다 (N-n=m)
        
        //즉, cnt[i]번 나타난 숫자 i는 튜플의 maxCnt - cnt[i]번째 원소이다
		answer[maxCnt - cnt[i]] = i;
	}

	return answer;
}

풀이 2

• 튜플을 표현하는 집합을 집합 크기 오름차순으로 정렬 후, 각 집합에 포함된 원소를 검사한다.
  이전 집합에 포함되어 있지 않은 새롭게 추가된 원소가 튜플에 다음으로 추가될 원소이다.

• 예. {{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}}가 주어진 경우
  -> {2}, {2, 1}, {1, 2, 3}, {1, 2, 4, 3} 집합 크기 오름차순 정렬
  -> 튜플 [2, 1, 3, 4]

#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <iostream>

using namespace std;

bool subvecCmp(vector<int> v1, vector<int> v2){
    return v1.size() < v2.size();
}

vector<int> solution(string s) {
    //s 맨 앞{, 맨 뒤} 제거
    s = s.substr(1, s.size()-2);
    //cout << s;

    
    vector<vector<int>> subvecV;
    
    vector<int> subvec;
    string substr = "";
    for(int i = 0; i<s.length(); ++i){
        if(s[i] == '{') continue;
        else if(s[i] == '}'){
            subvec.push_back(stoi(substr));
            substr = "";
            
            // for(int i = 0; i<subvec.size(); ++i){
            //     cout << subvec[i]<<" ";
            // }
            // cout << "\n";
            
            subvecV.push_back(subvec); 
            subvec.clear();
        }
        else if(s[i] == ','){
            //집합과 집합 사이 쉼표
            if(substr == "") continue;
            
            //숫자와 숫자 사이 쉼표
            subvec.push_back(stoi(substr));
            substr = "";
        }
        else{
            substr += s[i];
        }
    }
    sort(subvecV.begin(), subvecV.end(), subvecCmp); 
    
    
    vector<int> answer;
    set<int> includedInAnswer;
    
    for(int i = 0; i<subvecV.size(); ++i){
        for(int j = 0; j<subvecV[i].size(); ++j){
            int n = subvecV[i][j];
            if(includedInAnswer.find(n) == includedInAnswer.end()){
                answer.push_back(n);
                includedInAnswer.insert(n);
                break;
            }
        }
    }
    
    return answer;
}