★ [2] 튜플 (sort 정렬 람다, string append와 += 차이)

문제 설명

셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, 다음과 같이 표현할 수 있습니다.

(a1, a2, a3, ..., an)
튜플은 다음과 같은 성질을 가지고 있습니다.

중복된 원소가 있을 수 있습니다. ex : (2, 3, 1, 2)
원소에 정해진 순서가 있으며, 원소의 순서가 다르면 서로 다른 튜플입니다. ex : (1, 2, 3) ≠ (1, 3, 2)
튜플의 원소 개수는 유한합니다.
원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음과 같이 집합 기호 '{', '}'를 이용해 표현할 수 있습니다.

{{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}}
예를 들어 튜플이 (2, 1, 3, 4)인 경우 이는

{{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}
와 같이 표현할 수 있습니다. 이때, 집합은 원소의 순서가 바뀌어도 상관없으므로

{{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}
{{2, 1, 3, 4}, {2}, {2, 1, 3}, {2, 1}}
{{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}}
는 모두 같은 튜플 (2, 1, 3, 4)를 나타냅니다.

특정 튜플을 표현하는 집합이 담긴 문자열 s가 매개변수로 주어질 때, s가 표현하는 튜플을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

[제한사항]
s의 길이는 5 이상 1,000,000 이하입니다.
s는 숫자와 '{', '}', ',' 로만 이루어져 있습니다.
숫자가 0으로 시작하는 경우는 없습니다.
s는 항상 중복되는 원소가 없는 튜플을 올바르게 표현하고 있습니다.
s가 표현하는 튜플의 원소는 1 이상 100,000 이하인 자연수입니다.
return 하는 배열의 길이가 1 이상 500 이하인 경우만 입력으로 주어집니다.

 

[입출력 예]
s result
"{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4]
"{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4]
"{{20,111},{111}}" [111, 20]
"{{123}}" [123]
"{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1]
입출력 예에 대한 설명
입출력 예 #1
문제 예시와 같습니다.

입출력 예 #2
문제 예시와 같습니다.

입출력 예 #3
(111, 20)을 집합 기호를 이용해 표현하면 {{111}, {111,20}}이 되며, 이는 {{20,111},{111}}과 같습니다.

입출력 예 #4
(123)을 집합 기호를 이용해 표현하면 {{123}} 입니다.

입출력 예 #5
(3, 2, 4, 1)을 집합 기호를 이용해 표현하면 {{3},{3,2},{3,2,4},{3,2,4,1}}이 되며, 이는 {{4,2,3},{3},{2,3,4,1},{2,3}}과 같습니다.

---

키포인트

ㄴ 각 원소가 담긴 vector를 size순으로 오름차순 정렬하고

ㄴ 이때 정렬된 상태를 보면 처음에는 {a1}, {a2, a1}, {a1, a2, a3},, 뭐 이런식으로 들어가게 되는데,

a1이 첫번째 숫자이고, 두번째 그룹에서 a1를 제외한 a2가 두번째 숫자인 규칙이라고 보면 된다.

ㄴ 이중 포문을 돌리면서 answer에 넣고 없으면 추가한다.

#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

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

	s.erase(s.begin());
	s.erase(s.end() - 1);
	vector<vector<int>> vec;
	bool isCanSave = false;
	string tempStr;
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == '{')
		{
			vector<int> temp;
			isCanSave = true;
			vec.push_back(temp);
			continue;
		}
		else if (s[i] == '}')
		{
			vec[vec.size() - 1].push_back(stoi(tempStr));
			isCanSave = false;
			tempStr.clear();
			continue;
		}
		else if (s[i] == ',')
		{
			if (isCanSave)
			{
				vec[vec.size() - 1].push_back(stoi(tempStr));
				tempStr.clear();
			}

			continue;
		}

		tempStr.append(&s[i]);
	}

	map<int, bool> m;
	sort(vec.begin(), vec.end(), [](const vector<int>& fir, const vector<int>& sec) { return fir.size() < sec.size(); });
	for (int i = 0; i < vec.size(); i++)
	{
		for (int j = 0; j < vec[i].size(); j++)
		{
			// 이미 존재하면 넘기고, 없으면 추가하기
			if (m.find(vec[i][j]) != m.end())
				continue;
			else
			{
				answer.push_back(vec[i][j]);
				m.insert({ vec[i][j] , true });
			}
		}
	}

	return answer;
}

 

개선 사항

ㄴ 애초에 s 에서 숫자들을 뽑아올 때 해당 숫자의 빈도수를 map에 저장하고,

ㄴ 빈도수가 높은 순서부터 첫번째 숫자라고 생각하면 된다.

ㄴ 이때 전체 숫자 갯수 - 빈도수가 answer의 인덱스라고 보면 된다.

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

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

	s.erase(s.begin());
	s.erase(s.end() - 1);
	bool isCanSave = false;
	string tempStr;
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == '{')
		{
			isCanSave = true;
			continue;
		}
		else if (s[i] == '}')
		{
			m[stoi(tempStr)] += 1;
			isCanSave = false;
			tempStr.clear();
			continue;
		}
		else if (s[i] == ',')
		{
			if (isCanSave)
			{
				m[stoi(tempStr)] += 1;
				tempStr.clear();
			}
			continue;
		}

		tempStr += s[i];
	}

	int size = m.size();
	answer.resize(size);
	for (auto& iter : m)
		answer[size - iter.second] = iter.first;


	return answer;
}

 

 

- 계속 시간초과가 나길래, 이중포문으로 풀면 안되는 문제인 줄 알고 한참을 삽질했다.

정답 코드와 비교해보니, s 에서 숫자를 뽑을 때 str.append 를 사용했는데, 이것 때문에 시간 초과가 나고 있엇다.

(단순 for문에서 사용했는데도 시간초과라니)

앞으로는 무조건 += 를 사용해서 코테를 풀자!!

1. append는 메모리의 재할당 방식이 +=가 더 효율적으로 된다고 나와있다.

- append는 여러가지 데이터 형식을 처리할 수 있도록 설계되었기 때문에 더 복잡할 수 있다. (다목적 함수)

ㄴ 문자열을 전체 or 범위 or 다른 문자열 형식의 데이터 처리 같은 로직이 들어가기 때문에 더 많은 연산과 분기가 발생할 수 있다.

ㄴ 이때 메모리 복사 작업이 발생할 수 있기 때문에 성능이 차이가 발생한다.

- +=는 단일 문자나 문자열이라는 하나의 객체만 처리하기 때문에 내부에서 처리할 분기가 적다.

 

2. Sort의 사용자 정의 람다식 활용하기

sort(pairVec.begin(), pairVec.end(), [](pair< int, int> m1, pair<int, int> m2) -> bool
		{
			return m1.second > m2.second;
		});
        
[capture](parameter_list) -> return_type { body }

매번 찾지말고 형식을 기억하자 [](a, b) -> bool {}

[]: 외부 변수를 람다 함수 내부에서 사용할 수 있도록 캡처하는 부분

(a,b) : 람다 함수에 전달될 매개변수 목록

bool : 람다 함수가 반환하는 타입 (C++ 14 이후, 반환타입은 추론할 수 있어서 생략가능)

{} : 함수의 본문!