프로그래머스 - 튜플 - C++

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

프로그래머스

 

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

vector<int> solution(string s) {
    vector<int> answer;
    
    unordered_map<int,int> um;
    string temp="";
    
    for(char c : s)
    {
        if(isdigit(c))
            temp+=c;
        else if(!temp.empty())
        {
            um[stoi(temp)]++;
            temp="";
        }
    }
    
    vector<pair<int,int>> mv(um.begin(),um.end());
    
    sort(mv.begin(),mv.end(),
        [](const pair<int,int>&a,const pair<int,int>& b)
         {
             return a.second>b.second;
         });
    
    for(auto& item : mv)
        answer.push_back(item.first);
    
    return answer;
}

튜플을 표현하는 문자열이 주어질 때, 어떤 튜플인지를 리턴하는 문제이다. 

 

튜플이 [2,1,3,4] 면 {{2},{2,1},{2,1,3},{2,1,3,4}} 와 같이 표현할 수 있다. 

 

그럼 이 표현을 보고 어떤 튜플인지 알려면 각 집합에서 원소가 어떤 것이 있고 그 원소들이 몇번이나 나오는지 확인하면 된다. 

왜냐면 앞에 있는 숫자일 수록 더 자주 등장하기 때문이다. 

 

따라서 unordered_map을 사용해 구현한다. 

<어떤숫자, 얼마나 나오는가> 로 사용한다. 

string temp="";
    
    for(char c : s)
    {
        if(isdigit(c))
            temp+=c;
        else if(!temp.empty())
        {
            um[stoi(temp)]++;
            temp="";
        }
    }

위 반복문을 통해서 맵에 저장한다. 

숫자면 10의자리 이상일수 있기 때문에 temp에 저장하고 아니라면 맵에 저장한다. 

이 때, temp.empty() 일 때는 { 이거나 {} 바깥의 , 로 아직 숫자가 나오지 않은 상태이기 때문이다. 

또 {} 안에 , 는 isdigit으로 걸러진다. <- 즉 이 경우에 temp가 um에 저장된다. 

 

unordered_map, map 자료구조를 value 기준으로 정렬하려면 vector로 옮겨서 sort함수를 실행해야한다. 

 

따라서

vector<pair<int,int>> mv(um.begin(),um.end());
    
    sort(mv.begin(),mv.end(),
        [](const pair<int,int>&a,const pair<int,int>& b)
         {
             return a.second>b.second;
         });

다음과 같이 mv로 옮기고 sort를 실행한다. 이 때, 비교함수로 람다함수를 넘겨준다. a>b 형태가 내림차순 형태이다. 

 

그리고 정렬된 순으로 answer에 저장하면된다. 

 

처음 내가 풀었던 코드는 

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

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

vector<int> solution(string s) {
    vector<int> answer;
    vector<string> v;
    map<string, int> m;
    string ss = "";
    int n = 0;
    for (int i = 1; i < s.length() - 1; i++)
    {
        if (s[i] == '}')
        {
            m.insert({ ss,n }); ss = ""; i++; n = 0;
        }
        else if (s[i] != '{')
        {
            ss += s[i];
            if (s[i] != ',')n++;
        }
        
    }

    vector<pair<string, int>> mv(m.begin(), m.end());
    sort(mv.begin(), mv.end(), compare);

    unordered_set<string> us;
    for (const auto& item : mv)
    {
        vector<string> iv; ss = "";
        for (int i = 0; i < item.first.length(); i++)
        {
            if (item.first[i] == ',')
            {
                iv.push_back(ss); ss = "";
            }
            else ss += item.first[i];
        }
        iv.push_back(ss);
        for (int i = 0; i < iv.size(); i++)
        {
            if (us.find(iv[i]) == us.end())
            {
                us.insert(iv[i]);
                answer.push_back(stoi(iv[i]));
            }
        }
    }
    return answer;
}

이 코드이다. 훨씬 복잡해보이기도 하고 시간복잡도도 문자열이나 튜플이 길어지면 느려진다.

 

1. 간단하게 말하면 먼저 문자열을 각 집합으로 나눴다.

2. 그리고 각 집합에 대해서 <집합,원소의 개수> 로 map에 저장후 원소의 개수로 정렬을 한다. 

3. 정렬 후 각 map의 원소에 대해서 집합을 다시 , 기준으로 나눠서 set에 저장한다. 

4. 이 때, set에 없던 것이면 바로 answer에 저장하고 있던 것이면 패스한다. 

이렇게 한 이유는 원소의 개수로 정렬을 했기 때문에 원소의 개수가 작은 집합이 빈도수가 많은 숫자와 동일하기 때문이다. 

그렇지만 그 과정에서 문자열을 두번이나 slice하기 위한 for문을 돌기 때문에 비효율적이고 가독성도 떨어지기 때문에 

첫번째 코드로 하는 것이 더 효율적이라는 결론을 내렸다.