[STL] 알고리즘 문제

문제1)
이미 정렬된 두 정수형 배열 arr1과 arr2가 주어졌을 때, 두 배열에 공통으로 존재하는 원소만을 포함하는 배열을 반환하는 solution() 함수를 구현하시오.

vector<int> solution(vector<int> arr1, vector<int> arr2)
{
	vector<int> answer;
	vector<int>& longVec = arr1.size() > arr2.size() ? arr1 : arr2;
	vector<int>& shortVec = arr1.size() > arr2.size() ? arr2 : arr1;

	int shortVecIndex = 0;
	for (int i = 0; i < longVec.size(); i++)
	{
		if (longVec[i] == shortVec[shortVecIndex])
			answer.push_back(longVec[i]);
		else if (longVec[i] > shortVec[shortVecIndex])
		{
			shortVecIndex++;
			i--;
		}
	}

	return answer;
}

int main()
{
	vector<int> arr1 = {1,2,3,4,5,6,7,8,10};
	vector<int> arr2 = {2,6,8,9,10};
	vector<int> result = solution(arr1, arr2);

	for (int ele : result)
		cout << ele << endl;
}

---

문제2)
정수 n이 주어졌을 때, 각 자릿수를 오름차순으로 정렬하여 새로운 정수를 반환하는 solution() 함수를 구현하시오.

long long solution(long long n)
{
	multiset<byte> numSet;

	int num = n;
	do
	{
		int digit = num % 10;
		num = num / 10;

		numSet.insert(digit);
	} while (num > 0);

	long long answer = 0;
	int i = 1;
	for (int digit : numSet)
	{
		answer += digit * pow(10, numSet.size() - i);
		i++;
	}

	return answer;
}

int main()
{
	cout << solution(873211) << endl;
}

이런 식으로 숫자로 계산하지 말고 stoll을 이용해서 string으로 계산하면 3줄만 쓰면 된다.
다음부턴 그런식으로 하자

---

문제3)
문자열로 구성된 배열 strings와 문자 c가 주어졌을 때, c를 포함하는 문자열만 추려서 오름차순으로 정렬한 결과를 반환하는 solution() 함수를 구현하시오.

vector<string> solution(vector<string> arr, char c)
{
	vector<string> answer;
	for (int i = 0; i < arr.size(); i++)
	{
		size_t index = arr[i].find(c);
		if (index != string::npos)
			answer.push_back(arr[i]);
	}

	sort(answer.begin(), answer.end());
	return answer;
}

int main()
{
	vector<string> aaa = solution({"apple", "banana", "cherry", "date"}, 'a');
	for (string str : aaa)
		cout << str << endl;
}

---

문제4)
정수 배열 arr이 주어졌을 때, 연속된 숫자들이 가장 길게 이어지는 구간의 길이를 구하는 solution() 함수를 구현하시오.

int solution(vector<int> arr)
{
	sort(arr.begin(), arr.end());

	int answer = 0;
	int consecutiveNumbers = 0;
	int preNum = -1;
	for (int i = 0; i < arr.size(); i++)
	{
		if (preNum == -1 ||
			(arr[i] > preNum && arr[i] == preNum + 1))
		{
			preNum = arr[i];
			consecutiveNumbers++;
		}
		else if (consecutiveNumbers > answer)
		{
			answer = consecutiveNumbers;
			consecutiveNumbers = 0;
			preNum = -1;
		}
	}

	return answer;
}

int main()
{
	cout << solution({ 100,4,200,1,3,2 }) << endl;
}

다 좋은데 중복 숫자가 들어가 있을 때를 생각하지 않았다.
vector를 unique + erase를 쓰든 set을 쓰든 해야겠다.