[Algorithm] Programmers :: 튜플

https://school.programmers.co.kr/learn/courses/30/lessons/64065?language=cpp 

프로그래머스

bool cmp(const pair<int, int>& a, const pair<int,int>& b)
{
    return a.second > b.second;
}
 
vector<int> solution(string s) {
    vector<int> answer;
    map<int, int> checkMap;
    vector<pair<int, int>> v;
 
    int index = 0;
 
    while (index != s.size() - 2) // 끝에서 두번째.
    {
        string temp = "";
        
        if (isdigit(s[index]))
        {
            while (1)
            {
                if (isdigit(s[index])) // 숫자면
                {
                    temp += s[index];
                    index++;
                }
                else break;
            }
            int a = stoi(temp);
            checkMap[a]++;
        }
        else index++;
    }
 
    for (auto temp : checkMap)
    {
        v.push_back(make_pair(temp.first,temp.second));
    }
 
    sort(v.begin(), v.end(), cmp);
 
    for (int i = 0; i < v.size(); i++)
    {
        answer.push_back(v[i].first);
    }
 
    return answer;
}

 

주어지는 요소들로 올바르 튜플을 구하는 문제다. 운이 좋은건지 감이 좀 좋아진건지, 그래도 바로 어떻게 풀어야할지 포인트는 빨리 알아챘다.

(2,1,4,3) 이란 튜플이 있다면 이 원소들은 (2) , (2,1) , (2,1,4), (2,1,4,3) 이런식으로 구성된다. 각 원소내부의 순서도 바껴도 상관없다. 여기서 규칙은 (2,1,4,3)이란 튜플의 앞에 숫자부터 많이 포함되어있다는 것이다.

가장 앞에 숫자인 2는 n개(원소개수)만큼 카운팅된다. 그다음 1은 n-1개, 4는 n-2개.... 이렇게 내림차순으로 카운팅된다.

 

그렇기 때문에 주어진 문자열에서 숫자를 추출해서 카운팅한 다음, 카운팅값 기준으로 내림차순을 하고 리턴하면 된다.