프로그래머스 - 튜플(64065)

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

---

문제 설명

셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, 다음과 같이 표현할 수 있습니다.

(a1, a2, a3, ..., an)
튜플은 다음과 같은 성질을 가지고 있습니다.

중복된 원소가 있을 수 있습니다. ex : (2, 3, 1, 2)
원소에 정해진 순서가 있으며, 원소의 순서가 다르면 서로 다른 튜플입니다. ex : (1, 2, 3) ≠ (1, 3, 2)
튜플의 원소 개수는 유한합니다.
원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음과 같이 집합 기호 '{', '}'를 이용해 표현할 수 있습니다.
이 때 튜플은 순서가 바뀌어도 상관 없습니다.
{2, 1, 3, 4} → {{2}, {1, 2}, {3, 2, 1}, {4,2,1,3}}

특정 튜플을 표현하는 집합이 담긴 문자열 s가 주어질 때, s가 표현하는 튜플을 배열에 담아 return 해주세요.

---

코드

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

using namespace std;

bool compare(string s1, string s2){

    return s1.length() < s2.length();
}

vector<int> solution(string s) {
    vector<int> answer;
    set<int> ret;
    
    // 1
    s.erase(s.begin());
    s.erase(s.end()-1);
    
    vector<string> tuples;
    
    size_t nPos = s.find("{");
    size_t bracket = s.find("}", nPos);
    while(nPos != string::npos)
    {
        string nums = s.substr(nPos+1, bracket-nPos-1);
        tuples.push_back(nums);
        nPos = s.find("{", bracket+1);
        bracket = s.find("}", nPos);
    }
    
    //2
    sort(tuples.begin(), tuples.end(), compare);
    
    //3
    for(auto tuple : tuples)
    {

        nPos = tuple.find(",");
        if(nPos == string::npos)
        {
            ret.insert(stoi(tuple));
            answer.push_back(stoi(tuple));
            continue;
        }
        
        if(ret.find(stoi(tuple.substr(0, nPos))) == ret.end())
        {
            ret.insert(stoi(tuple.substr(0, nPos)));
            answer.push_back(stoi(tuple.substr(0, nPos)));
        }
        
        size_t beforeNPos = nPos;
        nPos = tuple.find(",", nPos+1);
        
        while(nPos != string::npos)
        {
            int tmp = stoi(tuple.substr(beforeNPos+1, nPos-beforeNPos-1));
            beforeNPos = nPos;
            nPos = tuple.find(",", nPos+1);
            
            if(ret.find(tmp) == ret.end()){
                ret.insert(tmp);
                answer.push_back(tmp);
            }
        }
        if(ret.find(stoi(tuple.substr(beforeNPos+1))) == ret.end())
        {
            ret.insert(stoi(tuple.substr(beforeNPos+1)));
            answer.push_back(stoi(tuple.substr(beforeNPos+1)));
        }
    }
    
    return answer;
}

/*
1. 문자열을 각 튜플을 나눔
2. 길이별 sort
3. 앞에서부터 읽으면 됨 
*/

---

아이디어

1. 문자열을 집합별로 분리한다.
2. 분리한 집합을 길이별로 정렬한다.
3. 집합을 앞에서부터 읽어, 새로 추가된 원소만 추가하면서 진행하면 최종적으로 완성된 튜플이 나온다.

아이디어를 거의 하드코딩한 것에 가까운...

for(char i: s){
        if(i-'0' >=0 && i-'0' <=9){
            tmp += i;
        }
        else{
            if(tmp.length())
                st[stoi(tmp)]++, tmp.clear();
        }
    }

방법으로 숫자만 모은 후, 해당 숫자에 개수를 모두 구하여, 가장 높은 횟수 == 가장 먼저오는 원소로 횟수가 원소 순서와 비례하니 정렬해 푸는 방식이 진짜 잘푸신 분이었다...