[C++] 프로그래머스 튜플

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

프로그래머스

풀이

주어진 s집합을 만들 수 있는 튜플을 구하는 문제입니다. 문제 조건에 따라 튜플에는 중복 원소가 존재하지 않습니다.

 

따라서, 맵 자료구조를 사용해 s를 돌면서 isdigit() 함수를 활용해 숫자를 해싱합니다.

 

해싱이 끝나면 튜플을 구성하는 원소를 알 수 있는데, 이 때 s집합에서 가장 많이 등장한 순서부터 정렬해야 합니다 

왜냐하면, 문제 예시처럼

• {a1, a2, a3, a4, ..., an} 이 주어질 때, {{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}} 와 같이 표현할 수 있고, 
• {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}} 와 같은 집합을 만들었다고 할 때, a1이 모든 부분집합에 포함되어야 하기 때문에 a1=2이어야 합니다. 나머지 또한 마찬가지로 가장 많이 등장한 횟수대로 a2=1, a3=3, a4=4 가 됩니다.  

 

따라서, 벡터 v에 해싱 된 값들을 옮긴 후, cmp함수를 사용해 등장 순서대로 정렬해서 answer에 추가해주면 됩니다. (Key 값 기준으로 정렬하기 팁). 

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

using namespace std;

bool cmp(pair<int, int>& a, pair<int, int>& b)
{
    return a.second > b.second;
}

vector<int> solution(string s) {
    vector<int> answer;
    unordered_map<int, int> hash;
    string num="";
    for (int i=0; i<s.size(); i++) {
        if (isdigit(s[i])) {
            num+=s[i];
        }
        else {
            if (num.size()>0) {
                hash[stoi(num)]++;
                num="";
            }
        }
    }
    vector<pair<int, int>> v(hash.begin(), hash.end());
    sort(v.begin(), v.end(), cmp);
    for (auto i:v) {
        if (i.second>0) answer.push_back(i.first);
    }
    return answer;
}