[프로그래머스] 2단계 - 튜플

문제 설명

특정 튜플을 표현하는 집합이 담긴 문자열 s가 표현하는 튜플을 배열에 담아 return

https://dev-juelee.tistory.com/manage/newpost/?type=post&returnURL=%2Fmanage%2Fposts%2F#

Tistory

 

문제 풀이법

튜플을 찾는 문제인데 사실 이해는 못했는데 잘 보면 규칙이 있다

바로 s에서 나온 수를 내림차순 하면 된다

 

예시로 "{{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}"가 있으면, 1은 2번, 2는 4번, 3은 2번, 4는 1번 나왔으므로 이를 내림차순하면 [2, 1, 3, 4]가 되는 것이다

 

따라서 map을 사용하여 해당 수가 몇번 나왔는지 count 해주었다

하지만 map에서는 내림차순 정렬을 할 수 없기에 vector<pair<int, int>> 형식을 통해서 map의 key와 value 값을 넣어준 후 내림차순하여 answer에 key 값을 넣어주었다

 

처음에는 map을 사용하지 않고 vector<pair<int, int>> 형식으로만 넣어줬는데, 그렇게 되면 key에 해당하는 value값에 +1 해주는 과정이 너무 복잡하고 또 segmentation 에러가 나와서 번거롭지만 map과 vector를 둘 다 사용하였다

 

 

소스 코드

#include <string>
#include <vector>
#include <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;
    
    map<int, int> m;
    vector<pair<int, int>> v;
    
    string str;
    
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '{')
            str = "";
        
        else if (s[i] == '}' || s[i] == ',') {
            if (str != "") {
                int key = stoi(str);
                m[key]++;
                str = "";
            }
        }
        
        else if (s[i] >= '0' && s[i] <= '9')
            str += s[i];
        
    }
    
    for (auto it = m.begin(); it != m.end(); it++) {
        int key = it->first;
        int value = it->second;
        
        v.push_back({key, value});
    }
    
    sort(v.begin(), v.end(), cmp);
    
    for (int i = 0; i < v.size(); i++) {
        answer.push_back(v[i].first);
    }
    
    
    return answer;
}