boj 10814 문제의 경우 만약 첫번째 인자까지만 고려해서 sort를 진행한다면 그냥 compare함수를 넣지 않고 sort를 사용해도 정답이 나왔어야 했다. 그런지 지속적으로 답이 안나오는걸 보니 두번째 인자도 비교해준다는 생각이 들어서 그와 관련된 내용을 검색해보았고, 내게 필요한 정보를 담고있는 블로그를 발견하였다.
https://caputdraconis.tistory.com/116
[C++] pair vector를 sort! 두번째값을 기준으로도 정렬 가능하다거!
vector v1; vector v2; vector v3; 좌표, 이름이 따로 있는 숫자 등을 담을 때 자주 쓰는 pair로 이루어진 벡터를 정렬하고자 한다..! // test.cpp #include using namespace std; int main() { vector v; v.push_back(make_pair(1, 2));
blog.caputdraconis.dev
이 블로그를 보면 첫번째 인자가 같을때, 두번째 인자에서 sort를 해주는걸 알 수 있다. 그렇기 때문에 이런 경우는 boj 10814분 문제에서 기본적인 sort를 사용하면 비교하지 말아야할 두번째 인자까지 비교해버리게 되는 것이다. 그래서 바로 stable_sort()를 사용하더라도 답이 나오지 않았던 것이다. 두번째 인자인 j로 시작하는 단어가 먼저 나와야 하는데 이때 기본적으로 오름차순 정렬로 두번째 인자까지 비교하기 때문에 d로 시작하는 단어가 먼저 나오게 정렬되어버리는 것이다.
그래서 compare 함수를 사용해서 딱 첫번째 인자까지만 비교해서 결과값을 sort하도록 만들어주는 것으로 보여진다.
이 내용이 결국 위에 블로그에서 내가 알아야 할 핵심 내용이고, 이 내용을 잊지 말도록 하자.
다음에 그리디 풀이에서 회의실 배정 문제에서도 pair를 활용하고 sort를 사용하는데, 그때 두가지 인자를 모두 비교한다는걸 명심하고 사용하도록 하자.
stable_sort() 함수를 사용해도 두번째 인자까지 비교해서 sort를 진행해줘서 그래서 그냥 기본인 stable_sort()를 10814문제에 사용해도 틀리는 것이었다.
이걸 한번 변경해보면,
이렇게 원하는 결과를 출력할 수 있다.
결국 이렇게 해서 boj 10814번 문제 같은 경우 첫번째 인자만 비교하고, 그리고 그것 조차도 stable_sort를 활용해서 두번째 인자의 요소는 원래 그 순서로 있도록 만들어서 문제를 풀면 되는 것이다.
compare 함수를 사용하는걸 잘 이용하도록 하자. 그리고 pair를 인자로 넘길때 sort, stable_sort함수의 경우는 두번째 인자까지 비교해서 순서를 맞추어준다는걸 잊지말고, 첫번째 인자만 비교하려면 compare 함수를 만들어서 인자로 넘겨줘서 sort시에 활용하도록 만들자.
'알고리즘 > BOJ' 카테고리의 다른 글
| c++ sort compare 함수를 어떻게 작성해야 하는가에 대하여. (0) | 2023.05.17 |
|---|---|
| c++ 알고리즘 문제 해결: radix sort에서, radix란? (0) | 2023.05.17 |
| const와 &의 사용에 관하여. (0) | 2023.05.16 |
| boj 10814번 문제를 풀며 만나게된, VLA를 사용한 코드와, 이 코드의 문제점과 개선사항. (0) | 2023.05.16 |
| boj 10814번 문제를 풀면서 만나게된 stl sort()의 stable과 unstable, 그리고 stl stable_sort()에 관하여. (0) | 2023.05.16 |
