프로그래머스 - 튜플 (C++)

Pixabay로부터 입수된 Gerd Altmann님의 이미지 입니다.

 

---

 

https://school.programmers.co.kr/learn/courses/30/lessons/64065

프로그래머스

 

 이번 문제는 특정 튜플을 표현하는 집합이 담긴 문자열 s가 주어졌을 때, s가 표현하는 튜플을 배열에 담은 값을 구하는 문제이다. 예를 들어, 튜플이 { 2, 1, 3, 4 }인 경우, 가능한 표현 집합은 { { 2 }, { 2, 1 }, { 2, 1, 3 }, { 2, 1, 3, 4 } } 이다. 그리고 문제의 s는 이 { { 2 }, { 2, 1 }, { 2, 1, 3 }, { 2, 1, 3, 4 } }를 문자열로 바꾼 "{ { 2 }, { 2, 1 }, { 2, 1, 3 }, { 2, 1, 3, 4 } }" 같은 값이다.  하지만 s는 { { 2 }, { 2, 1 }, { 2, 1, 3 }, { 2, 1, 3, 4 } }일 수도 있고 { { 2, 1, 3, 4 }, { 2 }, { 2, 1, 3 }, { 2, 1 } }일 수도 있다. 즉, 특정 튜플을 표현하는 집합의 원소들 순서는 랜덤이다. 그렇기에 올바른 튜플을 구하기 위해 이 점을 고려해야 한다.

 

 최우선으로 해야할 것은 s를 문자열에서 vector로 변경하는 것이다. 왜냐하면 문자열로 답을 구하기는 매우 까다롭기 때문이다. s를 vector로 변경하는 것은 크게 어렵지 않다.

 

vector<vector<int>> Parse(string s)
{
	vector<vector<int>> result;

	for (int i = 1; i < s.size() - 1; ++i)
	{
		if (s[i] == '{')
		{
			++i;

			vector<int> set;
			string num = "";

			while(true)
			{
				if (s[i] == '}')
				{
					int realNum = stoi(num);
					set.push_back(realNum);
					
					num = "";

					break;
				}
				else if (s[i] == ',')
				{
					int realNum = stoi(num);
					set.push_back(realNum);
					
					num = "";
				}
				else 
					num += s[i];

				++i;
			}

			result.push_back(set);
		}
	}

	return result;
}

위의 코드는 s를 vector<vector<int>> 타입으로 바꾸는 함수이다. 위의 코드를 간단히 설명하자면 다음과 같다.

• i는 문자열 s의 인덱스를 의미한다.
• s[i]가 '{'일 경우, 집합의 시작을 의미한다. 이 집합은 vector<int> set이다.
• s[i]가 '0'부터 '9'라면 숫자라는 뜻이기에 숫자를 기록한다.
• s[i]가 ','인 경우는 해당 숫자가 끝났고 다른 숫자가 온다는 뜻이기에 set에 숫자를 저장한다.
• 마지막으로 s[i]가 '}'라면 집합이 끝이라는 뜻이므로 반복문을 종료한다.

 

 

 이제 위의 코드에서 얻은 특정 튜플을 표현하는 집합을 이용해 답을 구해야 한다. 하지만 집합의 원소들은 순서가 랜덤이기에 이를 바로 이용할 수는 없다. 예를 들어, { { 2 }, { 2, 1 }, { 2, 1, 3 }, { 2, 1, 3, 4 } }이라는 vector<vector<int>> sets를 이용해 답 튜플을 구해보자. sets[0]부터 sets[3](마지막 요소)까지 하나씩 살펴볼 것이다. sets[0]은 { 2 }이므로 튜플에는 2가 포함되어 있을 것이다. 그리고 sets[1]은 { 2, 1 } 이며 2는 이미 존재한다는 것을 알고 있다. 그렇기에 튜플에 1을 추가한다. 이런 식으로 진행하면 { 2, 1, 3, 4 }라는 답을 얻을 수 있다.

 

 그러면 sets 중 가장 길이가 긴 요소가 답이 아닌가라고 생각할 수도 있다. 위의 예시에서 sets에서는 { 2, 1, 3, 4 }가 가장 길이가 길기에 바로 이 값을 반환하면 된다고 생각할 수도 있다. 하지만 튜플은 순서 역시 중요하다. 하지만 주어진 s의 집합들의 원소들은 순서가 보장되어 있지 않다. 예를 들어, 마지막 예제의 s는 { { 4, 2, 3 }, { 3 }, { 2, 3, 4, 1 }, { 2, 3 } }이다. 하지만 답은 { 2, 3, 4, 1 }이 아닌 { 3, 2, 4, 1 }이다. 즉, 일일이 답을 구해줘야 한다는 것이다. 

 

 그래서 이를 위해 sets를 정렬할 것이다. 정렬의 기준은 요소의 길이이다. 요소의 길이가 짧은 것이 앞으로 오게 정렬할 것이다. 정렬은 sort 메서드를 통해 쉽게 할 수 있다. 이것들을 고려한 답안 코드는 아래와 같다.

 

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

bool checked[100001];

bool Compare(vector<int> a, vector<int> b)
{
    return a.size() < b.size();
}

vector<vector<int>> Parse(string s)
{
	vector<vector<int>> result;

	for (int i = 1; i < s.size() - 1; ++i)
	{
		if (s[i] == '{')
		{
			++i;

			vector<int> set;
			string num = "";

			while(true)
			{
				if (s[i] == '}')
				{
					int realNum = stoi(num);
					set.push_back(realNum);
					
					num = "";

					break;
				}
				else if (s[i] == ',')
				{
					int realNum = stoi(num);
					set.push_back(realNum);
					
					num = "";
				}
				else 
					num += s[i];

				++i;
			}

			result.push_back(set);
		}
	}

	return result;
}

vector<int> solution(string s) {
    vector<int> answer;

    vector<vector<int>> sets = Parse(s);
    
    sort(sets.begin(), sets.end(), Compare);
    
    for (int i = 0; i < sets.size(); ++i)
    {
        vector<int> curTuple = sets[i];
        
        for (int k = 0; k < curTuple.size(); ++k)
        {
            int num = curTuple[k];
            
            if (checked[num] == false)
            {
                checked[num] = true;
                
                answer.push_back(num);
                
                break;
            }
        }
    }
    
    return answer;
}