[프로그래머스] 튜플 - c++

튜플

먼저 "{{2},{2,1},{2,1,3},{2,1,3,4}}" 형태의 튜플을 2차원 배열로 변환해줘야 한다.

따라서 처음에 문자열을 둘러싼 {{ }} 를 문자열에서 제거한다.

s = s.substr(2, s.size() - 4);

실행 후 2},{2,1},{2,1,3},{2,1,3,4 이런 형태가 되는데

각 튜플을 parts라는 배열에
["2", "2,1", "2,1,3", "2,1,3,4"] 형태로 저장하는 과정을 거쳐야 한다.

각 튜플이 끝나는 지점 ( }, 가 연달아오면 ) 그 전까지의 튜플 내용을 parts 에 원소로 추가하는 것을 반복한다.

마지막 튜플 원소는 조건과 맞지 않으므로 마지막에 저장된 튜플 내용 시작 시점부터 끝까지의 substring을 추출해 parts 배열에 따로 추가해준다.

vector<string> parts;
    int start = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '}' && i + 1 < s.size() && s[i + 1] == ',') {
            parts.push_back(s.substr(start, i - start));
            start = i + 3;
            i += 2;
        }
    }
    parts.push_back(s.substr(start));  // 마지막 원소 추가
    

parts 배열은
["2", "2,1", "2,1,3", "2,1,3,4"] 이 되고, 각 원소를 배열로 만들어 2차원 배열을 생성한다.

이때 배열의 각 원소를 stringstream을 이용하여 ','를 기준으로 분리해 배열에 int 형으로 저장한다.

    vector<vector<int>> tuples;
    for (string part : parts) {
        vector<int> nums;
        stringstream ss(part);
        string token;
        while (getline(ss, token, ',')) {
            nums.push_back(stoi(token));
        }
        tuples.push_back(nums);
    }

중복없이 배열의 길이가 작은 것부터 순서대로 추가해야하므로
배열의 길이 순으로 2차원 배열을 정렬한다.

 // 길이 순 정렬
    sort(tuples.begin(), tuples.end(), [](const vector<int>& a, const vector<int>& b) {
        return a.size() < b.size();
    });

unordered_set을 이용하여 배열의 각 원소가 이미 등장한 것인지 확인한다.
unordered_set s; 이 있다고 할때,
s.count(x) → x가 존재하면 1, 아니면 0을 반환한다

    // 중복 없이 순서대로 추가
    vector<int> answer;
    unordered_set<int> seen;
    for (const auto& vec : tuples) {
        for (int num : vec) {
            if (seen.count(num) == 0) {
                answer.push_back(num);
                seen.insert(num);
            }
        }
    }

이전 배열에 등장하지 않은 숫자를 하나씩 answer 배열에 추가하면 원래의 튜플 값을 얻을 수 있다.

전체 코드

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <unordered_set>

using namespace std;

vector<int> solution(string s) {
    s = s.substr(2, s.size() - 4);  // "{{...}}" 제거
    vector<string> parts;
    int start = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '}' && i + 1 < s.size() && s[i + 1] == ',') {
            parts.push_back(s.substr(start, i - start));
            start = i + 3;
            i += 2;
        }
    }
    parts.push_back(s.substr(start));  // 마지막 원소 추가

    // 문자열 → 숫자 벡터
    vector<vector<int>> tuples;
    for (string part : parts) {
        vector<int> nums;
        stringstream ss(part);
        string token;
        while (getline(ss, token, ',')) {
            nums.push_back(stoi(token));
        }
        tuples.push_back(nums);
    }

    // 길이 순 정렬
    sort(tuples.begin(), tuples.end(), [](const vector<int>& a, const vector<int>& b) {
        return a.size() < b.size();
    });

    // 중복 없이 순서대로 추가
    vector<int> answer;
    unordered_set<int> seen;
    for (const auto& vec : tuples) {
        for (int num : vec) {
            if (seen.count(num) == 0) {
                answer.push_back(num);
                seen.insert(num);
            }
        }
    }

    return answer;
}