백준 11650 (multiset)

11650번: 좌표 정렬하기

과정

• 정렬과 좌표를 보자마자 "sort"를 x좌표, y좌표에 대해 각각 1번씩 총 2번을 써야하나? 생각했다.
• 근데 기억하기론, sort(시작, 끝, 함수명)이었던걸로 기억하고, bool형 비교함수를 통해 T/F로 2개의 원소를 비교하여 오름차순으로 정리한다.
• 근데, 저번과 마찬가지로 sort쓰기 싫었다.(그냥 고집) 않이 sort쓸수 있는지 없는지를 공부할 필요는 없잖아?
• 그래서, 언리얼C++에서 배웠던 multimap이 기억났다.

Part1 11. 언리얼 컨테이너 라이브러리 UCL : UStruct, TMap

MultiMap : 튜플구조에 해시테이블 형태로 데이터 구축(동적배열 형태), 중복가능

• 그래서 여기부턴 c++ multimap에 대해 찾아봤다.

 

MultiMap

• multimap은 key와 value를 한 쌍으로 묶어서 저장하는 Map STL이다. 
• 기본적으로 정렬되면서 삽입! 중복된 키 가능!
• 하지만, key나 value 2가지 중 하나로만 정렬이 가능하다 → 문제와 맞지 않다.

MultiSet

• multiset은 multimap과 다르게 하나의 value만 가진다.(한 쌍이 아님)
• 나머지는 똑같음! 
• 그럼 이것도 사요할 수 없느냐? ㄴㄴ 이건 사용할 수 있다.
• 문제1. x, y값 한 쌍을 어떻게 만드느냐? : pair을 사용해서 2가지 값을 하나의 값으로 묶을 수 있다.
• 문제2. 이것도 결국 2쌍을 비교하면서 정렬은 힘들지 않냐? : 솔직히 이건 답을 못찾았다. 그래서 해보려고 한다.

코드

#include <iostream>

#include <set>

using namespace std;

int main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(nullptr);

    int N = 0;  // 입력 받을 좌표의 총 개수

    multiset<pair<int, int>> pairs;

    cin >> N;

    for (int i = 0; i < N; i++)

    {

        int X = 0;

        int Y = 0;

        cin >> X >> Y;

        pairs.insert(make_pair(X, Y));

    }

    for(auto p : pairs)

    {

        cout << p.first << ' ' << p.second << '\n';

    }

    return 0;

}

multiset 관련 초기화, intsert, 출력 방법은 아래 페이지를 참고했다.

Multiset of Pairs in C++ with Examples - GeeksforGeeks

 

결과는 놀랍게도 통과..

아마 내 예상으로는 multiset자체가 입력을 받을 때부터 정렬을 해준다는 점이 고려된거 같은데,

 

만일 multiset의 pair 정렬에 대해 자세히 아시는 분, 관련 링크를 아시는 분은 댓글로 알려주셨으면 한다.