[프로그래머스] 튜플 - LEVEL2

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 어떤 문제를 풀기 위한 논리보다는 입력으로 주어진 문자열을 사용할 수 있도록 가공하는 것이 주가 되는 문제인 것으로 보인다.

문제에 예시로 주어진 문자열인 {{2},{2,1},{2,1,3},{2,1,3,4}}을 살펴보면서 풀이해보겠다.

1) 문자열에서 {을 삭제해준다.
: 2},2,1},2,1,3},2,1,3,4}}

2) },을 /으로 교체해준다.
: 2/2,1/2,1,3/2,1,3,4/}

3) }을 삭제해준다.
: 2/2,1/2,1,3/2,1,3,4/

4) /을 기준으로 split 해서 split1 벡터의 각 원소로 저장한다.
: vector<string> split1 = {"2", "2,1", "2,1,3", "2,1,3,4"}

5) split1 벡터의 각 원소인 문자열들을 ,을 기준으로 split해서 숫자로 변환해 split2 벡터에 저장
: vector<vector<int>> split2 = [{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}]

6) split2 벡터를 각 원소의 숫자 개수 오름차순으로 정렬
: vector<vector<int>> split2 = [{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}]

7) split2 벡터의 가장 마지막 원소(가장 원소 개수 많은)를 확인해 해당 집합에 대한 튜플에 들어있는 숫자들의 개수를 numCount 벡터에 저장 (numCount[0]에는 0의 개수, numCount[1]에는 1의 개수 ...)
: vector<int> numCount(100000) = {0, 1, 1, 1, 1, 0, ...}

8) 튜플을 표현하는 집합들(== split2) 중 길이가 짧은 집합의 원소들부터 차례대로 확인

• 이전에 나오지 않은 숫자라면 (numCount[해당 원소] > 0) : answer 벡터에 추가
• 이전에 나온 숫자라면 (numCount[해당 원소] == 0) : 넘어감

9) 최종적으로 문자열이 표현하는 튜플이 answer에 담기게 되고, 이를 반환한다.

🖥️ 풀이 코드

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

using namespace std;	
vector<string> split1;
vector<vector<int>> split2;
vector<int> numCount(100000);
vector<int> answer;

vector<string> split(string input, char dlim)
{
	vector<string> result;
	stringstream ss;
	string stringBuffer;
	ss.str(input);
	while (getline(ss, stringBuffer, dlim))
	{
		result.push_back(stringBuffer);
	}
	return result;
}

vector<int> split_int(string input, char dlim)
{
	vector<int> result;
	stringstream ss;
	string stringBuffer;
	ss.str(input);
	while (getline(ss, stringBuffer, dlim))
	{
		result.push_back(stoi(stringBuffer));
	}
	return result;
}

bool compare(vector<int> v1, vector<int> v2)
{
	return v1.size() < v2.size();
}

vector<int> solution(string s)
{
	// '{' 삭제
	s.erase(remove(s.begin(), s.end(), '{'), s.end());	// remove 하면 해당 문자가 삭제됐을 때의 문자열 길이 기준으로 마지막 위치 리턴함 						// -> s.erase(remove(), s.end())하면 삭제된 부분의 길이만큼 사이즈 줄어듦.

	// "},"을 "/"으로 교체 
	while (s.find("},") != string::npos)
		s.replace(s.find("},"), 2, "/");

	// '}' 삭제
	s.erase(remove(s.begin(), s.end(), '}'), s.end());
	
	// '/' 기준 split해서 벡터 각 원소로 저장
	split1 = split(s, '/');

	// 각 문자열 ',' 기준 split 해서 숫자로 변환해 저장
	split2.resize(split1.size());
	for (int i = 0; i < split1.size(); i++)
		split2[i] = split_int(split1[i], ',');

	// 숫자 개수 오름차순으로 정렬
	sort(split2.begin(), split2.end(), compare);

	// 각 숫자 개수 저장
	for (int i = 0; i < split2[split2.size() - 1].size(); i++)
		numCount[split2[split2.size() - 1][i]] += 1;

	// 튜플을 표현하는 집합 중 길이가 짧은 것부터 확인해 이전에 나오지 않은 수라면 answer 벡터에 추가시키고, 이전에 나온 숫자라면 넘어감.
	for (int i = 0; i < split2.size(); i++)
	{
		for (int j = 0; j < split2[i].size(); j++)
		{
			int currentNum = split2[i][j];
			if (numCount[currentNum] > 0)
			{
				answer.push_back(currentNum);
				numCount[currentNum]--;
			}
		}
	}

	return answer;
}