[그리디] 튜플 - 2019 카카오 개발자 겨울 인턴십

해결 방법

Step1) 문자열을 파싱하여 각 집합을 벡터 v로 만들고, 벡터 v들로 이루어진 2차원 벡터 allv를 구성한다.

Step2) allv의 v들을 크기가 작은 순으로 정렬한다. allv를 구성하는 벡터들의 크기는 순서대로 1, 2, 3, ..., allv.size()가 될 것이다.

Step3) allv의 마지막 벡터를 이용하여 각 요소의 개수를 카운트 한다.

Step4) allv의 n번째 벡터에서 카운트(element_cnt)가 0이 아닌 요소를 answer의 n번째 요소로 넣고, 해당 요소의 카운트를 1 감소시키는 작업을 allv의 첫 번째 벡터부터 수행한다.

 

Step4 예시

{{1}, {2, 1}, {1, 2, 2}, {4, 1, 2, 2}}

-> 요소를 카운트해보면 1은 1개, 2는 2개, 4는 1개가 있다.

-> {1}에서 카운트가 0이 아닌 요소는 1이다(element_cnt[1]=1). 즉, answer의 1번째 요소는 1이 되고, element_cnt[1]의 값을 1 감소시킨다(element_cnt[1]=0)

-> {2, 1}에서 카운트가 0이 아닌 요소는 2다(element_cnt[2]=2). 즉, answer의 2번째 요소는 2가 되고, element_cnt[2]의 값을 1 감소시킨다(element_cnt[2]=1)

-> {1, 2, 2}에서 카운트가 0이 아닌 요소는 2다(element_cnt[2]=1). 즉, answer의 3번째 요소는 2가 되고, element_cnt[2]의 값을 1 감소시킨다(element_cnt[2]=0)

-> {4, 1, 2, 2}에서 카운트가 0이 아닌 요소는 4다(element_cnt[4]=1). 즉, answer의 4번째 요소는 4가 되고, element_cnt[4]의 값을 1 감소시킨다(element_cnt[4]=0)

 

 

소스 코드

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

vector<vector<int> > allv; // 모든 집합
vector<int> v; // 집합
vector<int> temp;
int element_cnt[100001]; // 요소의 개수 카운트
int open, comma;

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

vector<int> solution(string s) {
    vector<int> answer;
    for(int i=1;i<s.length()-1;i++){
        if(s[i]=='{') open=i; // 현재 '{' 인덱스 저장
        if(s[i]=='}'){
            if(comma==0) v.push_back(stoi(s.substr(open+1, i-open-1)));
            else v.push_back(stoi(s.substr(comma+1, i-comma-1)));
            allv.push_back(v);
            v.clear();
            comma=0; // ',' 인덱스 초기화
        }
        if(s[i]==','){
            if(s[i-1]=='}') continue;
            if(comma==0) v.push_back(stoi(s.substr(open+1, i-open-1)));
            else v.push_back(stoi(s.substr(comma+1, i-comma-1)));
            comma=i; // 현재 ',' 인덱스 저장
        }
    }
    
    sort(allv.begin(), allv.end(), cmp); // allv의 v들을 v의 크기가 작은 순으로 정렬
    
    temp = allv[allv.size()-1]; // 모든 요소를 포함하는 마지막 벡터
    for(int i=0;i<temp.size();i++) element_cnt[temp[i]]++; // 요소의 개수 카운트
     
    for(int i=0;i<allv.size();i++){
        temp = allv[i];
        // temp 벡터에서 카운트(element_cnt)가 0이 아닌 요소가 answer의 i번째 요소가 된다.
        for(int j=0;j<temp.size();j++){
            if(element_cnt[temp[j]]){
                answer.push_back(temp[j]);
                element_cnt[temp[j]]--;
            }
        }
    }
    return answer;
}

 

테스트케이스 15개 모두 정답