2차원 Vector Sort 방법

2D Vector Sort

코딩 문제를 풀기 위해서 2차원 Vector를 Sorting 해야 하는 경우가 있다. 특정 rule을 적용해 원하는 결과를 얻기 위해서 Vector가 Sorted 상태여야 하는 경우가 그렇다. 보통 Interval로 표현되는 문제들이 대표적인 예다. 

 

Cpp에서는 <algorithm> 헤더를 통해 기본적인 vector sort 기능을 제공한다. 기본 API는 1D vector를 입력받는 걸로 설계되어 있고, 2D vector나 정렬 조건을 customize 하고 싶은 경우가 생긴다.

 

아래는 2D vector를 1st idx 기준으로 sorting 하는 함수이다. 코딩 문제를 풀다보면 때떄로 필요하니 익혀놓자. (그냥 머리에 심어놓는게 편하다.)

 

bool cmp(vector<int> &v1, vector<int> &v2)
{
	if (v1[1] == v2[1])
		return v1[0] < v2[0];
	else
		return v1[1] < v2[1];
}

int main()
{
	vector<vector<int>>& points;

	// sort
	sort(points.begin(), points.end(), cmp);

	return 0;
}

예시 문제

 예시 문제를 풀어보고 싶으면 Leet Code 452. Minimum Number of Arrows to Burst Balloons를 풀어보자.

https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/?envType=study-plan-v2&envId=leetcode-75 

Minimum Number of Arrows to Burst Balloons - LeetCode