[C++] STL algorithm 조건 지정자

algorithm 메소드의 세 번째 인자는 사용자 정의 함수로 쓸 수 있다. sort의 경우 생략하면 자동으로 오름차순 정렬하기도 하지만 사용자가 정렬이나 find조건을 커스텀하는 경우에는 직접 조건을 지정해 주어야 한다.

 

comp함수가 참조값으로 전달되던 호출로 직접 전달되던 두 인자는 위치가 바뀌어서 첫 번째 인자가 b, 두 번째 인자가 a가  된다.

다음 예시를 보자.

먼저 일반적인 내림차순, 오름차순 정렬이다.

 

이제 조건을 더 추가해 보자.

1. 짝수가 홀수보다 앞에오도록 하기
2. 홀수끼리는 오름차순, 짝수끼리는 내림차순 정렬하기

#include<iostream>
#include<algorithm>

using namespace std;
int arr[] = { 1, 4, 2, 5, 8, 7, 6, 10, 9 };

bool comp(int a, int b) {
	cout << a << " " << b << endl;
	if (a % 2 == b % 2) return a < b;
	return a%2 < b%2+1;
}

int main(void) {
	sort(arr, arr + 9, comp);
	for (int& e : arr)cout << e << " ";
}

이게 어떻게 가능한거지?? 나도모름....algotirhm의 class가 어떻게 작성되어있는지 공식 문서를 보면서 참고하면 이해할 수 있지만 읽고싶지도 않고....봐도 모르겠다...일단 이렇게 쓰는구나..하고 익힌 다음 나중에 시간이 되면...찾아보자..!!!

1. pair의 두 쌍 모두 기준값 t보다 작거나 같을 경우만 find_if로 찾아주는 함수

#include <iostream>
#include <vector>
#include <algorithm>
#define F first
#define S second

using namespace std;
typedef pair<int, int> PII;

int N, M, H[2001][2002], T;
vector<PII> rec;
vector<PII> sta;

void solve() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M + 1; j++) {
            if (sta.empty() || H[i][j] > sta.back().F) sta.push_back({H[i][j], j});
            else if (H[i][j] == sta.back().F) continue;
            else {
                PII temp;
                int idx;
                while (!sta.empty() && H[i][j] <= sta.back().F) {
                    temp = sta.back();
                    idx = temp.S;
                    if (temp.F != 0) rec.push_back({temp.F, j - temp.S});
                    sta.pop_back();
                }
                sta.push_back({H[i][j], idx});
            }
        }
    }
    sort(rec.begin(), rec.end());
}

bool lessOrEqual(const PII p1, const PII p2) {
    return p1.F >= p2.F && p1.S >= p2.S;
}

bool go(const vector<PII>& r, const PII& t) {
    auto it = lower_bound(r.begin(), r.end(), t);
    return it == r.end() || !lessOrEqual(*it, t);
}

int main(void) {
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);

    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        string str;
        cin >> str;
        for (int j = 1; j <= M; j++) {
            if (str[j - 1] == '.')
                H[i][j] = H[i - 1][j] + 1;
            else
                H[i][j] = 0;
        }
    }
    solve();

    cin >> T;
    while (T--) {
        PII target;
        cin >> target.F >> target.S;
        if (go(rec, target))
            cout << "NO\n";
        else
            cout << "YES\n";
    }
}

정렬, 탐색, min, min, 

#include<iostream>
#include<vector>
#include<algorithm>
#define F first
#define S second

using namespace std;
typedef pair<int, int> PII;

int N, M, H[2001][2002], T;
vector<PII> rec;
vector<PII> sta;

void solve() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M + 1; j++) {
			if (sta.empty() || H[i][j] > sta.back().F) sta.push_back({H[i][j], j});
			else if (H[i][j] == sta.back().F) continue;
			else {
				PII temp;
				int idx;
				while (!sta.empty() && H[i][j] <= sta.back().F) {
					temp = sta.back();
					idx = temp.S;
					if(temp.F != 0)rec.push_back({temp.F, j - temp.S});
					sta.pop_back();
				}
				sta.push_back({ H[i][j], idx });
			}
		}
	}
}

bool lessOrEqual(const PII p1, const PII p2) {
	return p1.F >= p2.F && p1.S >= p2.S;
}

bool go(vector<PII> r, PII t) {

	auto ret = find_if(r.begin(), r.end(), [&](const auto& pair) {
		return lessOrEqual(pair, t);
		});

	return ret == r.end();
}


int main(void) {
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);

	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		string str;
		cin >> str;
		for (int j = 1; j <= M; j++) {
			if (str[j - 1] == '.') H[i][j] = H[i - 1][j] + 1;
			else H[i][j] = 0;
		}
	}
	solve();
	//sort(rec.begin(), rec.end());
	cin >> T;
	while (T--) {
		PII target;
		cin >> target.F >> target.S;
		if (go(rec, target)) cout << "NO\n";
		else cout << "YES\n";
	}

	//for (auto e : rec) cout << e.F << " " << e.S << "\n";


}

사용자 정의 함수

find

find_if

binary_search

 

...

 

 

두 개의 인자 비교도 가

 

사용자 정의 comp함수 좀 더 알아보기

https://howudong.tistory.com/205

[C++] 정렬(sort) 정렬 규칙을 직접 만드는 compare의 필요성과 사용법

https://leeeegun.tistory.com/5

[C++ STL] Sort() 사용법 및 compare 함수

https://artbooks.tistory.com/42

[STL] std::sort와 비교함수 오버라이딩

https://velog.io/@belog/C-STL-sorting

C++ STL sorting

https://dragondeok.tistory.com/11

C++ STL sort() 함수 다루기

https://blockdmask.tistory.com/178

[C++] sort algorithm 정리 및 예시