알고리즘 문제 풀다가 int key, int value 로 저장하고 이를 value 값을 기준으로 정렬할 일이 생겼다. 이를 해결한 내용을 기록으로 남기고 공유하고자 글을 쓴다.
풀던 문제 링크
www.hackerrank.com/challenges/jim-and-the-orders/problem?h_r=profile
key, value로 이루어진 객체를 value 값을 기준으로 sorting한다고 생각해보자, map을 이용하여 해쉬값을 저장하고 value값으로 이루어진 vector를 추가적으로 생성하는 방법이 있는데 이는 비교적 low레벨인 C++ 언어를 사용하는데 불필요한 일을 너무 많이 하는 것 같다고 느껴졌다.
찾아낸 방법이 비교 struct를 생성하고 이를 std::sort함수의 비교 함수 객체로(정렬하고자하는 조건이 담긴 객체) 넣어주는 것이다.
코드는 아래와 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Mystruct {
int key;
int value;
Mystruct(int k, int v) : key(k), value(v) {};
};
struct less_than_value {
inline bool operator() (const Mystruct& s1, const Mystruct& s2) {
return (s1.value < s2.value);
}
};
int main() {
vector<Mystruct> vec;
int i, n, temp1, temp2;;
cin >> n;
for (i = 1; i < n + 1; i++) {
cin >> temp1 >> temp2;
vec.push_back(Mystruct(i, temp1 + temp2));
}
sort(vec.begin(), vec.end(), less_than_value());
for (int i = 0; i < vec.size();i++) {
cout << vec[i].key << " ";
}
return 0;
}
|
cs |
위와 같이 key 와 value값이 있는 struct가 vector에 있다고 가정하자.
비교 객체함수 less_than_value에서 두 객체의 value값을 비교하여 bool값을 리턴한다.
따라서 sort(vec.begin(), vec.end(), less_than_value()); 코드를 실행하게 되면
(s1.value < s2.value)의 조건에 따라 vector는 value값을 기준으로 오름차순으로 정렬된다.
만약 여기서 value값이 동일한 경우 key값의 오름차순에 따라 정렬하는 조건을 추가적으로 넣고 싶다면 비교함수객체를 다음과 같이 바꾸면 된다.
|
1
2
3
4
5
6
7
8
9
10
|
struct less_than_value {
inline bool operator() (const Mystruct& s1, const Mystruct& s2) {
if (s1.value == s2.value) {
return(s1.key < s2.key);
}
else {
return (s1.value < s2.value);
}
}
};
|
cs |
s1.value와 s2.value가 같은 경우
s1.key 와 s2.key값을 비교하여 bool값을 리턴하여 조건을 추가한다.
이제 sort(vec.begin(), vec.end(), less_than_value()); 코드를 실행하게 되면
vector안의 struct 의 value 값을 기준으로 오름차순으로 정렬하는데 value값이 같은 경우 key값을 기준으로 오름차순으로 정렬하게 된다.
다음으로는 operater()부분 , std::sort에 대해 더 자세히 알아보도록 하겠다.
참고자료
https://en.cppreference.com/w/cpp/algorithm/sort
https://stackoverflow.com/questions/1380463/sorting-a-vector-of-custom-objects
댓글