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

프로그래머스의 튜플(Lv2) 문제이다.

[ 문제풀이 ]

집합이 담긴 문자열 S를 통해서, 해당 배열의 원본 형태를 구해야 하는 문제이다.

문제를 보고 가장 거슬렸던 것은 입력이 String 형태로 주어진다는 것이였다.

매개변수로 들어오는 string 변수에는 '{' , '}' , ',' 와 같은 문자들 또한 모두 포함되어 있어서 가장 먼저 이러한 문자들을

걸러내주는 작업을 진행하였다. 동시에 튜플들 중에서 '숫자'만 뽑아서 Vector에 저장해 주었다.

Vector를 Vector배열 형태로 선언해서, 각 크기에 맞는 인덱스에 들어가도록 구현하였다.

즉, vector<int> V[510] 이런식으로 선언을 해서 관리해 주었다.

가장 첫 번째 예를 들어보자.

{ { 2 } , { 2 , 1 } , { 2 , 1 , 3 } , { 2 , 1 , 3 , 4 }} 가 입력으로 주어진다.

그럼 가장 먼저 걸러줘야 할 문자들을 걸러냄과 동시에, '{ }' 안에 있는 숫자들만 추출해내는 작업을 진행해주었다.

위의 예시라면, 가장 앞에 '{' 문자 2개를 걸러내면 숫자 '2'가 처음으로 등장한다. 그 이후에, ' } ' 에 의해서 하나의 튜플이

끝나게 된다.

그렇게 되면 V[0]에 '2'를 push해주는 것이다.

그 이후에 ' , ' 를 지나, ' { ' 를 지나고 숫자가 나오게되는데, 이 때부터 ' } ' 까지 있는 모든 숫자들을 Vector에 넣어주는 것이다.

즉, 숫자 '2'와 '1'이 V[1]에 push될 것이다. 물론, 2와 1 사이에 있는 ',' 또한 걸러내주었다.

이런식이라면, V[2] = { 2, 1 , 3 } , V[3] = { 2, 1, 3, 4 } 가 될 것이다.

이 후, 가장 크기가 작은 Vector Index부터 찾아주면 된다.

가장 처음에는 '1'개 짜리를 찾으면 되는 것이다.

그럼 V[0] 에 '2'하나만 존재하므로 V[0]가 나오게 될 것이고, 정답 배열의 가장 첫 번째 원소는 '2'가 된다.

그 이후, 2개 짜리를 찾아보자. 그렇게 되면 V[1] = { 2 , 1 } 로 크기가 2인 Vector Index에 해당하고, 이 원소들을 탐색할 때,

이미 '2'는 한번 계산이 된 원소이므로 넘어가고 '1'인 원소가 남게 되므로 정답 배열의 두번째 원소는 '1'이 되는 것이다.

말로 설명하니 굉장히 어렵게 느껴질 수 있는데 소스코드를 한번봐보자.

먼저 걸러줘야 할 문자들을 거르면서, 숫자들만 Vector에 저장하는 과정이다.

vector<string> V[510];
int Idx = 0;
for (int i = 1; i < s.length(); i++)
{
    if (s[i] == '{')
    {
        string Temp = "";
        int j = i + 1;
        while (1)
        {
            if (s[j] == '}') break;
            if (s[j] == ',')
            {
                V[Idx].push_back(Temp);
                Temp = "";
                j++;
                continue;
            }
            Temp = Temp + s[j];
            j++;
        }
        V[Idx++].push_back(Temp);            
    }
}

가장 먼저, ' { ' 괄호를 찾아서 탐색을 시작한다. 왜냐하면 숫자가 나오기 위해서는 ' { ' 가 필요하기 때문이다.

line9 ~ 21) 을 보게 되면, ' } ' 괄호를 찾을 때 까지 반복하는 반복문이다.

즉, '{' 괄호가 나온 시점부터, '}' 가 나올 때 까지 ','을 제외한 숫자들만 Vector에 push해주는 것이다.

Vector에 저장된 값들을 통해서 실제 정답 배열의 원소들을 추출하는 부분은 다음과 같다.

while (1)
{
    bool Flag = false;
    for (int i = 0; i < Idx; i++)
    {
        if (V[i].size() == Len)
        {
            Flag = true;
            for (int j = 0; j < V[i].size(); j++)
            {
                int Num = stoi(V[i][j]);
                if (Visit[Num] == false)
                {
                    Visit[Num] = true;
                    answer.push_back(Num);
                }
            }
            Len++;
            break;
        }
    }
    if (Flag == false) break;
}

가장 작은 사이즈를 가진 Vector부터 찾아다니면서, "이미 선택한 원소를 제외한 나머지 원소들을" 정답배열의 원소로 채택하는

과정이다.

[ 소스코드 ]

#include<string>
#include<vector>
#include<algorithm>
using namespace std;
 
vector<int> solution(string s)
{
    bool Visit[100010] = { false, };
    vector<int> answer;
    vector<string> V[510];
    int Idx = 0;
    for (int i = 1; i < s.length(); i++)
    {
        if (s[i] == '{')
        {
            string Temp = "";
            int j = i + 1;
            while (1)
            {
                if (s[j] == '}') break;
                if (s[j] == ',')
                {
                    V[Idx].push_back(Temp);
                    Temp = "";
                    j++;
                    continue;
                }
                Temp = Temp + s[j];
                j++;
            }
            V[Idx++].push_back(Temp);            
        }
    }
    int Len = 1;
    while (1)
    {
        bool Flag = false;
        for (int i = 0; i < Idx; i++)
        {
            if (V[i].size() == Len)
            {
                Flag = true;
                for (int j = 0; j < V[i].size(); j++)
                {
                    int Num = stoi(V[i][j]);
                    if (Visit[Num] == false)
                    {
                        Visit[Num] = true;
                        answer.push_back(Num);
                    }
                }
                Len++;
                break;
            }
        }
        if (Flag == false) break;
    }
    
    return answer;
}