일단 이번에 접하게된 priority_queue에 인자로 넘겨주는 class를 구성하는 방법에 대해서는
현재 공부하고 있는 바킹독 알고리즘 강좌에서
class cmp {
public:
bool operator() (int a, int b) {
if(abs(a) != abs(b)) return abs(a) > abs(b);
return a > 0 && b < 0;
}
};
와 같은 형태로 제시해주어서 이 형태로 먼저 공부를 했었는데,
이와 관련하여서 새롭게 블로그 들을 찾아보면서 어떤식으로 해결하였는가 추가적으로 공부하였을때,
struct cmp{
bool operator() (int a, int b){
if(abs(a)==abs(b)) return a>b;
else return abs(a)>abs(b);
}
};
처럼 구조체를 넘겨주는 형태의 코드가 있어서 이걸 통해서 클래스를 넘겨주어도 되고, 구조체를 넘겨주어도 된다는걸 알 수 있었다.
실질적으로 코드에서 클래스로 선언되어 넘겨주는 cmp를 구조체로 선언해서 위와 같은 형태로 작성해서 똑같이 넘겨주어도 통과하는걸 볼 수 있었다.
위와 같은 구조체로 작성하고 통과하는 것에 대한 소스는
[C++][BOJ 백준]11286_절댓값 힙
문제 번호 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아
jaekwan.tistory.com
위의 블로그에서 정보를 얻을 수 있었다.
이때에
bool oprerator() (int a, int b){
....
}
형태로 작성되어 있는데, 이때에 사용하는 operator() 에 대해서 찾아보았다.

이러한 내용을 얻을 수 있었는데,
이 부분에 대해서는 깊이감있게 공부하기 보다는 이런것이 있다는것,
그리고 priority_queue에 넘겨줄때는 class 혹은 struct 형태로 operator() 를 넣어서 작성한 형태로 만들어서
넘겨주어야 한다는 부분까지 이해하고 사용하도록 하자.
현재는 알고리즘 문제 풀이에 초점을 맞추어서 진행하고 있으니까 이정도 선까지 학습을 한뒤에 다음에 여유 있을때 차근차근 깊이감있게 들어가도록 하자.
그리고 현재 내가 이해한 바로는,
int a, int b 순서로 compare 함수 코드를 작성할때,
마치 이해를 하기에는
a1, a2, a3, a4, a5, ... 형태로 진행하는 배열에서
int a1, int a2 순서로 넣어서 서로를 비교하고, return 에 사용하는 대소비교 형태로 서로의 원소들이 정렬되도록
하는 방향으로 매칭시켜서 결과가 나온다고 파악하고, 그때에 priority_queue는 queue이기 때문에 왼쪽을 입구로, 오른쪽을 출구로 놓은 형태의 큐에서, 오른쪽에서 top, pop 을 진행하는 형태로 매칭시켜서 암기하면 결과에서는 원하는 결과를 얻을 수있다는것이다.
순전히 이 방법은 암기를 위한 형태의 매칭이며, 실질적으로 내부 구현이 이렇게 받아들인 두 인자 int a 와 int b 가 왼쪽부터 오른쪽 순으로
이루어진 것은 아니며, 이걸 직접 출력을 찍어보면 오히려 서로 반대로, int a가 int b 보다 오른편 원소 였던것으로 기억한다.
하지만 이 형태의 암기법은 과거에 sort에 compare 함수를 넣을때부터 배열의 시작이 왼쪽부터 오른쪽으로 진행한다고 생각할때 매칭시켜서 외우던 방법이고, 만약 이 글을 누군가가 본다면 그 형태로 외울때 사용하던 방법과 똑같이 이번에 priority_queue를 진행할때도 적용되며, 단순히 queue의 출구 부분을 배열의 맨 오른쪽으로 둔다고 생각하고 위와 같은 방법을 같은 맥락으로 적용할 수 있다는 암기방법으로만 이해해주길 바란다.
실질적으로 int a가 어떤걸 받는지, int b가 어떤걸 받는지는 compare 함수 내부에 cout 형태로 해서 a, b를 출력해보면 알 수 있고, 이 암기방법과는 반대로 적용되었던 것으로 기억한다. 그래서 아마 실질적으로는 시작이 오른쪽부터 진행이 왼쪽으로 가는 배열을 생각해야 정확히 들어맞겠지만, 일반적으로 배열이라 하면 왼쪽부터 오른쪽으로 진행되는 형태로 배우는게 일반적이기 때문에 위에 사용한 방법은 그저 항상 옳바른 결과를 얻기 위한 암기방법이라고만 이해해주길 바란다.
이처럼 priority_queue의 경우도 배열이 왼쪽부터 오른쪽으로 진행하면서, 의도한 결과가 오른쪽 배열의 끝에서 top, pop 될수 있게 만드는 형태라고 생각하고,
그래서 최대 힙의 경우 기본이 less를, 최소 힙의 경우 greater를 넣어서 맨 오른쪽 배열의 끝이 가장 큰값이 되면 최대 힙, 가장 작은 값이 되면 최소 힙이 된다고 생각하도록 하자.
그리고 이번 문제에서처럼, 가장 오른쪽 값을 위와 같은 내가 원하는 형태의 cmp 클래스 혹은 구조체를 만들어서 넘겨주어서 설정할 수 있다.
그리고 만약 그런 방법에서 잘 이해가 안가고 어떤식으로 만들어야 할지 잘 모르겠다면, 내가 cmp를 넘겨주지 않고 풀었던 방법처럼,
개별적으로 양수를 받을 최소힙과 음수를 받을 최대힙을 만들어서 두 priority_queue를 이용해서 문제를 푸는 방법도 충분히 괜찮은 풀이라는 생각이 든다. 물론 풀이는 더 길어지지만 그렇게라도 풀어낼 수 있으니 염두해 두도록 하자.