다른 글
[C++, STL] 알고리즘 문제풀이를 위한 벡터(vector)
서론
벡터에 들어갈 수 있는 자료형에 pair와 struct(구조체)가 있다. 이들을 이용하여 하나의 원소에 다수의 자료가 들어갈 수 있다. pair와 struct를 자료형으로 가지는 벡터에서 사용자 지정 함수를 이용하면 특정 자료를 기준으로 정렬할 수 있다.
pair 벡터 정렬
정수를 자료형으로 갖는 pair의 first를 1차, second를 2차로 오름차순 정렬한다.
정렬전
- first : 3, 1, 1, 2, 3
- second: 4, 1, -1, 2, 3
정렬 후
- first : 1, 1, 2, 3, 3
- second : -1, 1, 2, 3, 4정렬은 STL의 sort를 이용한다. sort는 정렬의 기준을 정하는 비교함수가 필요하다. first, second 순으로 오름차순 정렬하거나 내림차순 정렬하는것은 STL에 포함되어있는 greater, less를 이용할 수 있고 first는 오름차순인데 second는 내림차순이거나 하는 것들은 직접 비교함수를 구현해야 한다.
greater, less를 이용한 정렬
헤더파일 추가
벡터는 vector, pair는 algorithm 헤더파일에 있다.
네임스페이스는 std이다.
#include <vector> #include <algorithm> using namespace std;
벡터 선언
pair를 자료형으로 갖는 vector를 선언한다.
vector<pair<int, int>>v;
정렬 실행
정렬은 STL의 sort를 이용한다. 정렬 범위는 벡터의 begin, end 함수를 사용하며 정렬 조건은 greater, less를 이용한다.
less는 생략이 가능하다.
sort(v.begin(), v.end()); // 오름차순 sort(v.begin(), v.end(), less<>()); // 오름차순 sort(v.begin(), v.end(), greater<>()); // 내림차순
사용자 정의 비교함수를 이용한 정렬
헤더파일 추가
벡터는 vector, pair는 algorithm 헤더파일에 있다.
네임스페이스는 std이다.
#include <vector> #include <algorithm> using namespace std;
벡터 선언
pair를 자료형으로 갖는 vector를 선언한다.
vector<pair<int, int>>v;
비교함수 구현
정렬은 STL의 sort를 이용한다. sort는 algorithm 헤더파일에 있다.
sort의 인자로 필요한 비교함수를 구현한다.
bool compare(pair<int, int>a, pair<int, int>b) {
if (a.first == b.first) {
return a.second < b.second;
}
else {
return a.first < b.first;
}
}
정렬을 위해서는 현재 원소와 다음원소의 크기를 비교하고 정해진 비교 규칙에 따라서 둘을 swap 하는 과정이 필요하다. 위 compare 함수에서 a는 현재 원소이고 b는 다음 원소인데, compare의 리턴 값이 false면 swap 한다.
priority_queue의 비교연산자와 swap 조건이 반대인데, 이유를 찾지 못했다.
a와 b의 first 값을 1차로 비교하여 오름차순으로 정렬하고, 만약 두 값이 같다면 second를 2차로 비교하여 오름차순으로 정렬한다. 내림차순으로 정렬하려면 리턴값의 부등호만 반대로 바꾸면 된다.
오름차순 : a.second < b.second
내림차순 : a.second > b.second
정렬 실행
sort(v.begin(), v.end(), compare);
전체코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(pair<int, int>a, pair<int, int>b) {
if (a.first == b.first) {
return a.second < b.second;
}
else {
return a.first < b.first;
}
}
void init(vector<pair<int, int>> &v){
v.push_back({3, 4});
v.push_back({1, 1});
v.push_back({1, -1});
v.push_back({2, 2});
v.push_back({3, 3});
}
int main(){
vector<pair<int, int>>v;
init(v);
sort(v.begin(), v.end(), compare);
for(auto i : v){
cout<<i.first<<" "<<i.second<<endl;
}
}
구조체 벡터 정렬
구조체 s의 score를 기준으로 1차 오름차순 정렬하고, age을 기준으로 2차 오름차순 정렬한다.
정렬 전
- age : 24, 27, 24, 36, 17
- score : 82, 73, 73, 90, 63
- name : 김, 이, 박, 최, 정
정렬 후
- age : 17, 24, 27, 24, 36
- score : 63, 73, 73, 82, 90
- name : 정, 박, 이, 김, 최헤더파일 추가
벡터는 vector 헤더파일에 있다.
네임스페이스는 std를 이용한다.
#include <vector> using namespace std;
구조체 선언
이름을 s로 갖는 구조체를 선언한다.
typedef struct {
int age;
int score;
string name;
}s;
벡터 선언
구조체를 자료형으로 갖는 벡터를 선언한다.
vector<s>v;
비교함수 구현
정렬은 STL의 sort를 이용한다. sort는 algorithm 헤더파일에 있다.
sort의 인자로 필요한 비교함수를 구현한다.
bool compare(s a, s b) {
if (a.score == b.score) {
return a.age < b.age;
}
else {
return a.score < b.score;
}
}
socre를 기준으로 1차로 오름차순 정렬하고 만약 score의 두 값이 같다면 age를 기준으로 2차 오름차순 정렬한다.
compare 함수의 동작 원리는 위의 pair 벡터 정렬을 참고한다.
내림차순으로 정렬하려면 리턴값의 부등호를 반대로 바꾼다.
정렬 실행
sort(v.begin(), v.end(), compare);
전체 코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
typedef struct {
int age;
int score;
string name;
}s;
bool compare(s a, s b) {
if (a.score == b.score) {
return a.age < b.age;
}
else {
return a.score < b.score;
}
}
void init(vector<s> &v){
v.push_back({24, 82, "김"});
v.push_back({27, 73, "이"});
v.push_back({24, 73, "박"});
v.push_back({36, 90, "최"});
v.push_back({17, 63, "정"});
}
int main(){
vector<s>v;
init(v);
sort(v.begin(), v.end(), compare);
}