[programmers] Lv.2 튜플(c++)

간단하게 끝낼 수 있는것은 간단하게 해결하자!! 는 생각이었다.

#include <string>
#include <vector>
#include <regex>

using namespace std;

vector<vector<int>> split(string str){
    smatch match;
    vector<vector<int>> res;
    while(regex_search(str, match, regex("(\\d|,)+"))){
        string matched = match.str();
        str = match.suffix().str();
        str = str.substr(2);
        
        smatch number;
        vector<int> inside;
        while(regex_search(matched, number, regex("\\d+"))){
            inside.push_back(stoi(number.str()));
            matched = number.suffix().str();
        }
        res.push_back(inside);
    }
    return res;
}

bool cmp(vector<int> v1, vector<int> v2){
    return v1.size() < v2.size();
}

vector<int> solution(string s) {
    vector<int> answer;
    vector<vector<int>> splited = split(s);
    sort(splited.begin(), splited.end(), cmp);
    
    for(auto vec : splited){
        for(auto v: vec){
            if(find(answer.begin(), answer.end(), v) == answer.end())answer.push_back(v);
        }
    }
    
    return answer;
}

좀 더 예쁘고 깔끔하게 할 수 있는 방법이 있지 않을까 생각해보니 하나 더 solution을 생각할 수 있었다.

이 코드의 설명은 아래 코드에 주석으로 있다.

더 빠르지 않을까 생각했는데 vector를 사용하는것도 map을 사용하는것도 위 코드보단 느렸다.

#include <string>
#include <vector>
#include <regex>
#include <map>

using namespace std;

bool cmp(pair<int, int> m1, pair<int, int> m2){
    return m1.second > m2.second;
}

// map에 cnt 값을 표시하는 방법
vector<int> solution(string s) {
    vector<int> answer;
    map<int, int> cnt;
    
    smatch match;
    while(regex_search(s, match, regex("(\\d)+"))){
        int number = stoi(match.str());
        s = match.suffix().str();
        
        // 맵에 해당 값의 cnt를 증가
        cnt[number]++;
    }
    vector<pair<int, int>> cnt_vec(cnt.begin(), cnt.end());
    // 가장 앞의 숫자가 가장 많이 언급됐을 것
    sort(cnt_vec.begin(), cnt_vec.end(), cmp);
    
    for(auto vec : cnt_vec)
        answer.push_back(vec.first);
    
    return answer;
}

// vector에 cnt값을 표시하는 방법
vector<int> solution(string s) {
    vector<int> answer;
    vector<int> cnt(100001, 0);
    vector<int> number; // 어떤 숫자가 들어있는지 확인해줘야함
    
    smatch match;
    while(regex_search(s, match, regex("(\\d)+"))){
        int num = stoi(match.str());
        s = match.suffix().str();
        
        if(cnt[num]==0) number.push_back(num); // 처음 숫자가 발견됐을 때 추가해주면 됨
        cnt[num]++;
    }
    vector<pair<int, int>> cnt_vec;
    // 각 숫자의 cnt 값을 pair로 만들어서 cnt_vec로 만들어주고 나머지는 위와 동일
    for(int n: number){
        cnt_vec.push_back({n, cnt[n]});
    }
    sort(cnt_vec.begin(), cnt_vec.end(), cmp);
    
    for(auto vec : cnt_vec)
        answer.push_back(vec.first);
    
    return answer;
}

---

문제

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

코딩테스트 연습 - 튜플

728x90

---

[접근]

1. 나누고

2. 정렬하고

3. 이미 들어있는지 확인하고 집어넣고 (속도 제한 있으면 set이나, 100,000크기의 array나 vector를 사용할까 생각하고 있었으나, 속도 제한이 없었다.)

---

[접근1] 나누고

나 왜이렇게 regex 좋아하지.. 졸업과제 때문인가?

regex("(\\d|,)+" 를 사용하면, { }안의 숫자와 컴마로 구성된 string을 뽑아 올 수있다.

뽑아온 string에서 숫자만 구분해서 벡터에 넣어준 후, 그 벡터를 벡터에 넣어준다.

vector<vector<int>> split(string str){
    smatch match;
    vector<vector<int>> res;
    while(regex_search(str, match, regex("(\\d|,)+"))){
        string matched = match.str();
        str = match.suffix().str();
        str = str.substr(2);
        
        smatch number;
        vector<int> inside;
        while(regex_search(matched, number, regex("\\d+"))){
            inside.push_back(stoi(number.str()));
            matched = number.suffix().str();
        }
        res.push_back(inside);
    }
    return res;
}

---

[접근2] 정렬하고

vector 사이즈가 작은것이 앞에 오게끔 정렬한다.

bool cmp(vector<int> v1, vector<int> v2){
    return v1.size() < v2.size();
}

sort(splited.begin(), splited.end(), cmp);

---

[접근3] 이미 들어있는지 확인하고 집어넣고

구한 이중 벡터를 돌면서, 안에 같은 숫자가 없으면 집어넣는것을 반복한다.

for(auto vec : splited){
    for(auto v: vec){
        if(find(answer.begin(), answer.end(), v) == answer.end())answer.push_back(v);
    }
}