백준 2910번 빈도정렬 (C++)(stable, unordered_map, find와 find_if,람다식,stable_sort)

문제

와 정말 정말 오래걸린 문제이다.

살짝 부끄럽지만 일단은 내가 vector, pair ,stable_sort, map ,unordered_map,find,find_if 등에 대해서 공부하는 시간이 됐다.

정답 코드

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <unordered_map>
using namespace std;


bool my_sort(pair<int,int> a,pair<int,int> b)
{
	return (a.second > b.second);
}

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	int n,c;
	cin >> n >> c;
	vector<pair<int ,int >>arr;
	int num;
	for (int i=0;i < n;i++)
	{
		cin >> num;
		auto a = find_if(arr.begin(),arr.end(), [&num](const pair<int, int>& elem){ return elem.first == num;});
		if (i == 0 || a == arr.end())
		{
			arr.push_back({num,1});
		}
		else
			a->second++;
	}
	stable_sort(arr.begin(),arr.end(),my_sort);
	for (auto it : arr)
	{
		for (int i=0; i < it.second;i++)
		{
			cout << it.first<< " ";
		}
	}
}

문제 풀이의 흐름

• 풀이 흐름은 간단하다.

• pair벡터 베열에 첫번째 요소는 숫자, 두번째 요소는 그 숫자의 갯수를 의미한다.

• 만약 pair에 이 값이 있는지 확인하고 값이 존재한다면 갯수를 늘려주고, 아니라면 새롭게 1개로 푸쉬를 한다.

• 이 과정을 반복해주고 처음 들어온 순서를 보존하면서 갯수가 큰 순으로 정렬을 해주고

• 그 정렬한 값만큼 쭉 출력을 해준다.

주의 할 점

find와 find_if()

find 함수

template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& val);

와 같은데 이건 맨 마지만 val 인자의 타입 T에 ==이 정의 되어 있어야만 사용할 수 있다.

하지만 pair같은 경우 first 와 second를 비교 할 거라서 꼭 find_if()함수를 써줘야만 한다.

find_if() 함수

template <class InputIterator, class UnaryPredicate>
InputIterator find_if(InputIterator first, InputIterator last, \
UnaryPredicate pred);

맨 마지막 pred 인자에 내가 원하는 조건식(bool 리턴값을 가지는)을 작성해서 넣어주면 됩니다.

pair 구조체에는 operator== 가 정의되어 있지 않아서 find를 사용하면 같은 값을 찾을 수 없습니다.

틀린코드

auto a = find(arr.begin(),arr.end(),num);

수정 코드

auto a = find_if(arr.begin(),arr.end(), \
	[&num](const pair<int, int>& elem){ return elem.first == num;});

수정 된 코드를 보면 아에 모르는 개념이 등장하는데 [&num] 이게 뭐냐?

C++11 이상에서 람다 식(종종 람다 라고도 함)은 함수에 인수로 호출되거나 전달되는 위치에서 익명 함수 개체( 클로저 )를 정의하는 편리한 방법입니다. 일반적으로 람다는 알고리즘 또는 비동기 함수에 전달되는 몇 줄의 코드를 캡슐화하는 데 사용됩니다.

람다식

1. capture 절 (C++ 사양의 람다 소개자 라고도 함)

2. 매개 변수 목록 선택적. ( 람다 선언자라고도 함)

3. 변경 가능한 사양 선택적.

4. exception-specification 선택적.

5. trailing-return-type 선택적.

6. 람다 본문입니다.

Capture 절

[ ] 이렇게 빈 캡쳐절을 사용하는 건 람다 식의 본문이 바깥쪽 범위 변수에 엑세스 하지 않는 것을 의미합니다.

그리고 이 안에 넣는 변수가 [&A] 로 넣을수도 있고 [A] 이렇게 값으로 엑세스 할 수도 있다. 그 외에 이렇게도 사용이 가능한데

[&total, factor]
[factor, &total]
[&, factor]
[=, &total]

C++ 람다 식

C++11 이상에서 람다 식(종종 람다라고도 함)은 함수에 인수로 호출되거나 전달되는 위치에서 익명 함수 개체( 클로저)를 정의하는 편리한 방법입니다. 일반적으로 람다는 알고리즘 또는 비동기 함수에 전달되는 몇 줄의 코드를 캡슐화하는 데 사용됩니다. 이 문서에서는 람다를 정의하고 다른 프로그래밍 기술과 비교합니다. 해당 장점을 설명하고 몇 가지 기본 예제를 제공합니다.

https://learn.microsoft.com/ko-kr/cpp/cpp/lambda-expressions-in-cpp?view=msvc-170

이 이상의 내용은 레퍼런스를 참고하도록 하자.

stable_sort()

stable_sort 함수는 여러 값들이 묶여 있을 때 하나의 요소로 정렬 할 때 다른 요소들의 정렬 순서도 정렬 전과 같이 유지 될 수 있도록 하는 정렬입니다.

#include <algorithm>
bool my_sort(pair<int,int> a,pair<int,int> b)
{
	return (a.second > b.second);
}

stable_sort(arr.begin(),arr.end(),my_sort);

사용은 sort와 비슷하게 사용이 됩니다.

또 stable_sort가 sort보다 빠르며, 유용하게 쓰일 때가 있다.

인자로 비교하는 함수에 레퍼런스 타입을 넣어주게 되면 컴파일 에러가 난다.

bool my_sort(pair<int,int> &a,pair<int,int> &b)

비교 함수를 이렇게 만들었었는데 자꾸 에러가 나서 레퍼런스를 지웠더니 컴파일이 됐다.

이렇게 const를 붙혀도 된다.

bool my_sort(const pair<int,int> &a,const pair<int,int> &b)
{
	return (a.second > b.second);
}

이게 되는 이유는 함수의 전달인자가 반드시

bool cmp(const Type1 &a, const Type2 &b);

이렇게 생겨야 하기 때문이다.

반성 및 고찰

오답코드

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <unordered_map>
using namespace std;


int my_sort(pair<int,int> &a,pair<int,int> &b)
{
	return (a.second >= b.second);
}

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	int n,c;
	cin >> n >> c;
	unordered_map <int,int> arr;
	int num;
	for (int i=0;i < n;i++)
	{
		cin >> num;
		arr[num]++;
	}
	vector<pair<int,int>> v(arr.begin(),arr.end());
	sort(v.begin(),v.end(),my_sort);
	for (auto it : v)
	{
		for (int i=0; i < it.second;i++)
		{
			cout << it.first<< " ";
		}
	}
}
//unordered map은 자동으로 정렬이 되지 않지만 그렇다고 입력된 순으로 값을 저장하고 있지 않다는 성질이 있어서 위의 코드가 틀렸었습니다

unordered_map은 자동으로 정렬이 되지 않지만 그렇다고 입력된 순으로 값을 저장하고 있지 않다는 성질이 있어서 위의 코드가 틀렸었습니다

위 코드는 unordered_map을 정렬하는 부분도 있지만 이건 stable하지 않아서 잘 쓸일은 없을 것 같아요.

이 문제는 안 써본 것들에 대한 많은 공부가 된 문제입니다.

Uploaded by N2T