[프로그래머스] 튜플

geonmyung·2020년 7월 27일
0
post-thumbnail

2019 카카오 개발자 겨울 인턴십 - 튜플

풀이

튜플의 첫 번째 원소가 들어간 집합의 크기는 1, n번째 원소까지 들어간 집합의 크기는 n이므로 각 배열을 길이 순서대로 정렬했다.
그리고 집합의 길이가 1인 첫 번째 배열부터 순서대로 보면서 answer 벡터에 값을 추가해줬다.


문제에서는 중복되는 원소가 없는 튜플이 주어진다고 했는데 문제를 잘 못 읽어 중복되는 원소가 나오는 경우까지 고려해서 코드를 작성했다.
만약 중복되는 원소가 없다면 set을 사용하여 문제를 풀 수 있을 것 같다.
다음에 다르게 풀어봐야겠다.

다른 방법

(7월 28일 내용추가!)
이 문제에 나오는 튜플은 중복되는 원소가 없으므로 set을 이용한 방법으로도 풀 수 있다.

반성

※ 문제를 잘 읽자!

코드

첫 번째 풀이

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

bool cmp(vector<int> &v1, vector<int> &v2){
    return v1.size() < v2.size();
}
vector<int> solution(string s) {
    vector<vector<int>> v;
    vector<int> answer;
    vector<int> tmp;
    
    int len = (int)s.size();
    string sub_part = "";
    //
    for(int i = 1 ; i < len - 1 ; i++){
        if(s[i] == ','){
            if(sub_part != ""){
                tmp.push_back(stoi(sub_part));
                sub_part = "";
            }
        }
        else if(s[i] == '}'){
            tmp.push_back(stoi(sub_part));
            sub_part = "";
            v.push_back(tmp);
            tmp.clear();
        }
        else if(s[i] != '{') sub_part += s[i];
    }
    // 정렬 완료
    sort(v.begin(), v.end(), cmp);
    
    answer.push_back(v[0][0]);
    // vector<vector>> v순회하기
    int arr_len = (int)v.size();
    for(int i = 1 ; i < arr_len ; i++){
        map<int, int> m;
        for(auto &it : answer) m[it]++;
        for(auto & it : v[i]){
            if(m[it]-1 < 0 || !m.count(it)){
                answer.push_back(it);
                break;
            }
        }
        //
    }
    //
     return answer;
}

다른 방법 풀이

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

bool cmp(vector<int> &v1, vector<int> &v2){
    return v1.size() < v2.size();
}
vector<int> solution(string s) {
    vector<vector<int>> v;
    vector<int> answer;
    vector<int> tmp;
    
    int len = (int)s.size();
    string sub_part = "";
    //
    for(int i = 1 ; i < len - 1 ; i++){
        if(s[i] == ','){
            if(sub_part != ""){
                tmp.push_back(stoi(sub_part));
                sub_part = "";
            }
        }
        else if(s[i] == '}'){
            tmp.push_back(stoi(sub_part));
            sub_part = "";
            v.push_back(tmp);
            tmp.clear();
        }
        else if(s[i] != '{') sub_part += s[i];
    }
    // 정렬 완료
    sort(v.begin(), v.end(), cmp);
    
    answer.push_back(v[0][0]);
    set<int> check_duplicate;
    check_duplicate.insert(v[0][0]);
    
    int arr_len = (int)v.size();
    for(int i = 1 ; i < arr_len ; i++){ // [2,1] [2,1,3] [2,1,3,4]
        for(int &j : v[i]){
            if(!check_duplicate.count(j)){
                check_duplicate.insert(j);
                answer.push_back(j);
            }
        }
    }
    return answer;
}
profile
옹골찬 개발자가 되기 위한 험난한 일대기

0개의 댓글