![백준 11650 (multiset)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fdjcazt%2FbtsFYoNGXCj%2Fvvsm3UcII1f2vDF0BgJN10%2Fimg.png)
11650번: 좌표 정렬하기
첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.
www.acmicpc.net
과정
- 정렬과 좌표를 보자마자 "sort"를 x좌표, y좌표에 대해 각각 1번씩 총 2번을 써야하나? 생각했다.
- 근데 기억하기론, sort(시작, 끝, 함수명)이었던걸로 기억하고, bool형 비교함수를 통해 T/F로 2개의 원소를 비교하여 오름차순으로 정리한다.
- 근데, 저번과 마찬가지로 sort쓰기 싫었다.(그냥 고집)
않이 sort쓸수 있는지 없는지를 공부할 필요는 없잖아? - 그래서, 언리얼C++에서 배웠던 multimap이 기억났다.
Part1 11. 언리얼 컨테이너 라이브러리 UCL : UStruct, TMap
언리얼 구조체 UStruct : 관련 프로퍼티(변수)를 체계화, 조작할 수 있는 데이터 구조체 https://docs.unrealengine.com/5.3/ko/structs-in-unreal-engine/ 구조체 게임플레이 클래스용 구조체 생성 및 구현에 대한 레
ssin-estella.tistory.com
MultiMap : 튜플구조에 해시테이블 형태로 데이터 구축(동적배열 형태), 중복가능
- 그래서 여기부턴 c++ multimap에 대해 찾아봤다.
MultiMap
- multimap은 key와 value를 한 쌍으로 묶어서 저장하는 Map STL이다.
- 기본적으로 정렬되면서 삽입! 중복된 키 가능!
- 하지만, key나 value 2가지 중 하나로만 정렬이 가능하다 → 문제와 맞지 않다.
MultiSet
- multiset은 multimap과 다르게 하나의 value만 가진다.(한 쌍이 아님)
- 나머지는 똑같음!
- 그럼 이것도 사요할 수 없느냐? ㄴㄴ 이건 사용할 수 있다.
- 문제1. x, y값 한 쌍을 어떻게 만드느냐? : pair을 사용해서 2가지 값을 하나의 값으로 묶을 수 있다.
- 문제2. 이것도 결국 2쌍을 비교하면서 정렬은 힘들지 않냐? : 솔직히 이건 답을 못찾았다. 그래서 해보려고 한다.
코드
multiset 관련 초기화, intsert, 출력 방법은 아래 페이지를 참고했다.
Multiset of Pairs in C++ with Examples - GeeksforGeeks
A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
www.geeksforgeeks.org
결과는 놀랍게도 통과..
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
아마 내 예상으로는 multiset자체가 입력을 받을 때부터 정렬을 해준다는 점이 고려된거 같은데,
만일 multiset의 pair 정렬에 대해 자세히 아시는 분, 관련 링크를 아시는 분은 댓글로 알려주셨으면 한다.
'개발 > 알고리즘 문제풀이' 카테고리의 다른 글
백준 1463 (점화식) (1) | 2024.03.23 |
---|---|
백준 1012 (DFS) (2) | 2024.03.23 |
백준 10989 (0) | 2024.03.20 |
백준 2839 (그리디) (0) | 2024.03.19 |
백준 2751 (정렬) (0) | 2024.03.18 |
이것저것 기억하고 싶은거 글쓰는 블로그
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!