[프로그래머스] 튜플

문제 링크

 

풀이

주어진 문자열을 적절히 파싱하여 정수형으로 변환했습니다. 그다음에는 규칙을 찾았는데요. 주어진 집합에서 사이즈가 1인 경우를 찾는 게 가장 먼저 진행돼야 합니다. 이것이 튜플의 첫 번째 원소에요. 그다음에 사이즈가 2인 것을 찾으면 다른 하나가 두 번째 원소가 되죠. 이를 위해 집합을 정수형으로 바꾼 벡터를 사이즈의 오름차순으로 정렬을 한 뒤에 차례대로 찾아서 넣어줬습니다. answer 변수에 넣은 값을 판별하기 위해 vector<bool>을 이용했습니다. vector<bool>은 부분 특수화가 되어 있습니다. true/false 정보만 담으면 되므로 bitwise로 최적화됐습니다.

 

s의 길이가 최대 백 만이므로 여유있게 vector<bool> 변수의 공간을 백 만개로 잡았습니다. 정적으로 선언하면 백 만 바이트(1mb)가 필요하지만 vector<bool>로 만들어 sizeof로 계산해보면 24가 출력됩니다. "혼자 연구하는 C/C++"에 따르면 vector<bool>은 표준에 포함되어 있긴 하지만 몇 가지 문제가 있고 컴파일러마다 지원 범위가 달라 사용을 가급적 자제하라고 되어 있습니다. cppreference를 보면 모든 컨텐이너 혹은 시퀀스 컨테이너의 요구사항을 필수적으로 충족하고 있진 않고 부스트에선 bool에 대해 특수화를 하지 않았다고 합니다. 안전성을 생각하면 안 써야 할 것 같지만 이 문제를 푸는 데는 지장이 없는 것 같아 사용했습니다.

 

코드

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

vector<int> solution(string s) 
{    
    vector<int> answer;
    size_t size = s.size();
    vector<vector<int>> numbers;
    vector<int> nums;
    string str;
    for (size_t i = 1; i < size - 1; ++i)
    {
        char c = s[i];        
        if (c == '}')
        {
            numbers.push_back(nums);
            nums.clear();
        }
        else if(c >= '0' && c <= '9')
        {
            str += c;
            if (s[i + 1] == ',' || s[i + 1] == '}')
            {
                nums.push_back(stoi(str));
                str = "";
            }
        }
    }
    if (numbers.size() == 1)
        return numbers[0];
    sort(begin(numbers), end(numbers), [](vector<int>& a, vector<int>& b) {
        return a.size() < b.size();
        });
    vector<bool> flag(1000000, false);
    for (size_t i = 0; i < numbers.size(); ++i)
    {
        for (size_t j = 0; j < numbers[i].size(); ++j)
        {
            auto n = numbers[i][j];
            if (flag[n] == false)
            {
                answer.push_back(n);
                flag[n] = true;
            }
        }
    }
    return answer;
}