알고리즘교안 p121 구조체를 담은 우선순위큐 질문
안녕하세요 교안공부중에 모르는 부분이 있어 질문드립니다.
교안 p121을 보면 구조체를 담은 우선순위큐에서 따로 sort()등의 함수를 사용하지 않고 데이터를 .push() 만 했을 뿐인데 출력하니 구조체 안에 선언된 연산자 오버로딩에 따라 정렬된 값을 출력하더라구요
어떤 방식으로 이게 가능한건가요? 우선순위 큐 자료구조만의 특징인가요? 이해가 잘 되지 않아서 vector를 이용하여 같은 방식으로 해보니 따로 정렬이 되지 않더라구요
교안 P121에 나온 '구조체를 담은 우선순위큐' 코드
#include <bits/stdc++.h>
using namespace std;
struct Point{
int y, x;
Point(int y, int x) : y(y), x(x){}
Point(){y = -1; x = -1; }
bool operator < (const Point & a) const{
return x > a.x;
}
};
priority_queue<Point> pq;
int main(){
pq.push({1, 1});
pq.push({2, 2});
pq.push({3, 3});
pq.push({4, 4});
pq.push({5, 5});
pq.push({6, 6});
cout << pq.top().x << "\n";
return 0;
}
제가 작성한 vector를 이용한 코드는 다음과 같습니다
#include <bits/stdc++.h>
using namespace std;
struct Point {
int y, x;
Point(int y, int x) : y(y), x(x) {}
Point() { y = -1; x = -1; }
bool operator < (const Point & a) const {
return x > a.x; // x 멤버변수를 기준으로 내림차순 정렬
}
};
vector<Point> v;
int main() {
v.push_back({1, 1});
v.push_back({2, 2});
v.push_back({3, 3});
v.push_back({4, 4});
v.push_back({5, 5});
v.push_back({6, 6});
for(auto a : v) cout << a.y << " : " << a.x << '\n';
return 0;
}
앞쪽에 보면 operator 연산자 오버로딩을 구조체안에 선언하지 않고 따로 cmp함수로 만들어 sort() 함수에 3번째 인자로 넣어서 정렬하는것은 이해하였습니다.
위의 코드에서 제가 잘못 작성한 부분이 있어서 정렬이 안되는건지, 아니면 우선순위큐 자료구조만 가능한 코드인것인지 아니면 아예 제가 뭔가를 잘못 이해하고 있는건지 잘 모르겠습니다.ㅠ
답변 1
1
안녕하세요 명운님 ㅎㅎ
vector는 기본적으로 자동정렬을 하지 않습니다. 그저 어떠한 요소를 넣는 바구니인 것이죠.
그러나 priority_queue, 즉 우선순위는 자동정렬을 합니다. 어떤 요소를 넣는다고 했을 때 해당 operator를 기반으로 자동정렬하는 자료구조입니다.
자료구조가 다르기 때문에 이러한 현상이 일어나는 것입니다.
감사합니다.
2-T 질문
0
6
0
코딩 살구클럽 가입 문의
0
67
2
코딩살구클럽 가입문의
0
69
2
3-K private case 질문
0
66
2
안녕하세요. 코딩살구클럽 문의드립니다!
0
78
2
7:41 듣다가 질문합니다
0
77
2
코드 리뷰 요청드립니다!
0
83
2
코딩살구클럽 계정 문의
0
79
2
SK하이닉스 대비 강의수강
0
217
3
코딩살구클럽 등록부탁드립니다.
0
78
2
7-F 재귀로 풀시 런타임애러
0
75
1
1-N 문제 질문입니다. (+ 채점오류)
0
82
2
코딩살구클럽 가입 확인 부탁드립니다.
0
86
2
직장인 코테 합격 공부방법 문의
0
127
2
코딩살구클럽 가입 방법
0
96
2
6-H 체점 관련 질문
0
74
1
채점서버 연결 관련 질문입니다
0
101
2
삼성 s직군
0
88
1
삼성 코테 없어짐
0
213
1
코딩살구클럽 가입부탁드립니다
0
87
2
코딩살구클럽 가입 요청 확인부탁드립니다
0
69
2
5-S 테스트 케이스 질문
0
78
2
코살 문제풀이 환경
0
88
2
2 - T 오큰수 문제가 있는 것 같습니다.
0
82
1





