프로그래머스 - 튜플 (Lv.2)

문제 링크

• 튜플

문제 접근1

• 가변벡터(board)를 이용해서 길이가 1~n인 집합들의 원소를 담는다.
• 길이가 짧은 순서대로 탐색하며, 이전 배열에 없던 원소들을 하나씩 answer에 담는다.

구현(All Pass)

#include <string>
#include <vector>
#include <iostream>
#include <cctype>
#include <algorithm>

using namespace std;

vector<int> board[1001];

void set_elements_on_board(string s){
    vector<int> v;
    string str;
    for(int i=0; i<s.length(); i++){
        if(s[i] != '{' && s[i] != '}' && s[i] != ','){
            str.push_back(s[i]);
        }
        else if(s[i]==',' && str.size()>0){
            v.push_back(stoi(str));
            str.clear();
        }
        else if(s[i]=='}' && str.size()>0){
            v.push_back(stoi(str));
            str.clear();
            int len = v.size();
            for(int i=0; i<len; i++)
                board[len].push_back(v[i]);
            v.clear();
        }
    }
}

vector<int> solution(string s) {
    vector<int> answer;
    
    // init
    s = s.substr(1);
    s.pop_back();
    set_elements_on_board(s);
    
    int n = 1;
    while(true){
        if(board[n].size()==0) break;
        for(int i=0; i<board[n].size(); i++){
            if(find(answer.begin(), answer.end(), board[n][i]) == answer.end()){
                answer.push_back(board[n][i]);
            }
        }
        n++;
    }
    
    return answer;
}

• 무식하게 풀기 방법…

문제 접근2

• 집합에서 가장 많이 나오는 원소 순서대로 answer 배열에 담는다.

구현(All Pass)

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cctype>

using namespace std;

bool cmp(pair<int, int> p1, pair<int, int> p2){
    return p1.second > p2.second;
}

vector<int> solution(string s) {
    vector<int> answer;
    
    string str;
    map<int, int> table;
    for(int i=0; i<s.length(); i++){
        if(isdigit(s[i])) str.push_back(s[i]);
        else if(str.size()>0){
            int ele = stoi(str);
            str.clear();
            if(table.find(ele)==table.end())
                table[ele] = 0;
            else
                table[ele] += 1;
        }
    }
    vector<pair<int, int>> v(table.begin(), table.end());
    sort(v.begin(), v.end(), cmp);
    for(int i=0; i<v.size(); i++)
        answer.push_back(v[i].first);
    
    return answer;
}