프로그래머스 (C/C++) 64065 : 튜플

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

프로그래머스

 

---

풀이

1. 받은 문자열을 집합 단위로 자른다.

2. 집합을 하나씩 탐색하며 담긴 수를 벡터에 int형으로 담아준다.

3. 2의 벡터들을 하나의 벡터에 담는다.

4. 담은 벡터들을 원소 벡터의 길이가 오름차순이 되게 정렬한다.

5. 정렬된 벡터들을 앞에서부터 탐색하며 ans(답안) 배열에서 찾을 수 없는 수라면 ans 배열에 담고, 해당 원소(벡터)의 탐색을 중단한다.

 

먼저 받은 문자열을 튜플 단위로 자르기 위해 '{' 과 '}'을 기준으로 잘라줬다.

이를 받아 ','  단위로 잘라 수를 구했고, 이 배열들을 벡터에 담아 vector<vector<int>> 형 벡터에 담아줬다.

해당 벡터를 벡터의 원소의 개수의 오름차순으로 정렬하였고,

이를 앞에서부터 탐색하며 나오지 않은 값이 발견되면 answer에 넣어주는 방식으로 풀었다.

 

---

 

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

다른 분의 풀이(위의 링크에서 맨 위의 풀이)에서 10만까지의 int형 배열을 만들고, 수가 나올 때마다 해당 배열의 위치를 카운트해줬다.

앞에 나온 숫자일수록 카운트해진 횟수가 많아지므로 이를 정렬하면 튜플의 순서를 구할 수 있다.

이 방법도 좋은 것 같아 링크를 첨부했다.

---

코드

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

vector<vector<int>> V;

void push_vec(string s){
    int i = 0;
    vector<int> A;
    while(i < s.size()){
        int now = i;
        while(i < s.size() && s[i] != ',') i++;
        A.push_back(stoi(s.substr(now, i - now)));      
        i++;
    }
    V.push_back(A);
}

void get_arr(string s){
    int i = 1;
    while(i < s.size()){
        if(s[i] == '{'){
            int start = i + 1;
            while(s[i] != '}') i++;
            push_vec(s.substr(start, i - start));
        }
        else i++;
    }
}

vector <int> get_ans(){
    vector <int> ans;
    int len = V.size();
    
    for(int i = 0; i < len; i++){
        for(int j = 0; j <= i; j++){
            if(find(ans.begin(), ans.end(), V[i][j]) == ans.end()){
                ans.push_back(V[i][j]);
                break;
            }
        }
    }
    return ans;
}

bool cmp(vector<int> a, vector<int> b){
    return a.size() < b.size();
}

vector<int> solution(string s) {
    get_arr(s);
    sort(V.begin(), V.end(), cmp);
    return get_ans();
}