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

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

코딩테스트 연습 - 튜플

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

vector<vector<int> > v(500);

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

void split(string s){
    int cnt=0;
    string temp;
    for (int i=1; i<s.size()-1; i++){
        if (s[i]=='{'){
            for (int j=i+1; s[j]!='}'; j++){
                if (s[j]==',') continue;
                temp="";
                while (isdigit(s[j])){
                    temp+=s[j];
                    j++;
                }
                v[cnt].push_back(stoi(temp));
                j--;
            }
            cnt++;
        }
    }
}

vector<int> solution(string s) {
    vector<int> answer;
    map<int, bool> visit;
    //문자열 처리 & v 구성
    split(s);
    //v sort
    sort(v.begin(), v.end(), cmp);
    for (int i=0; i<v[v.size()-1].size(); i++){
        visit[v[v.size()-1][i]]=false;
    }
    //v 돌아다니면서 체크
    for (int i=0; i<v.size(); i++){
        for (int j=0; j<v[i].size(); j++){
            if (!visit[v[i][j]]){
                answer.push_back(v[i][j]);
                visit[v[i][j]]=true;
            }
        }
    }
    return answer;
}

문자열을 split하여 각 {}에 있는 숫자들을 각 vector에 넣어준다. 

split 할 때는 숫자가 아닐때까지 읽어들여 읽어들인 문자열을 정수로 변환하여 vector에 넣어주었다.

 

이후, 각 vector들을 길이에 따라 정렬한다.

길이에 따라 오름차순으로 정렬된 vector 다. 

 

vector를 돌아다니면서 체크한다. 길이가 작은 것부터 순차적으로 돌아가면서 체크한다. 여기서 visit 이라는 map을 만들어서 해당 숫자를 아직 미방문한 상태이면 그것을 answer 벡터에 넣고, 방문 표시를 한다.

 

다른 분들의 풀이를 보니, 숫자가 나온 횟수를 세서 구할 수도 있다.

등장한 숫자를 모두 s[숫자]++ 한 후, vector<pair<int,int> > 에 (숫자, 등장한 횟수) 를 넣어준다. 이걸 내림차순으로 정렬하면 튜플을 구할 수 있다. (튜플의 왼쪽에 있는 숫자일수록 등장횟수가 더 많음을 응용)