5장 정렬 - (2) 11650번 좌표 정렬하기

-pair를 사용하면 편하다.

1. pair 

1) 정의

이름이 'first', 'second' 인 두 개의 변수를 저장할 수 있는 struct

2) 용도

-이차원 배열의 인덱스

-이차원 좌표평면에서의 좌표 (V)

-정점 번호와 해당 정점 번호까지의 최단거리를 묶어서 저장해야 되는 경우

3) 사용법

// pair 선언 및 생성

pair<int, int> p = make_pair(1, 2);

//pair의 멤버 변수에 접근

int valA = p.first;

int valB = p.second;

2. vector

1) 정의

사이즈가 유동적인 배열

2) 용도

-배열을 사용하는 모든 경우

3) 사용법

-<vector> include

4) 멤버 함수

v.size() : 사이즈 리턴

v.resize(new_size) : 사이즈 변경

v.empty() : 사이즈가 0인지 확인

v.begin() : 0번째 원소의 iterator 리턴

v.end() : 마지막 원소의 iterator 리턴

v.front() : 0번째 원소 리턴

v.back() : 마지막 원소 리턴

v.push_back(val) : 원소 추가

v.pop_back() : 마지막 원소 삭제

v.clear() : 모든 원소 삭제

5) 활용

<algorithm> 의 reverse 함수를 사용하면 vector에 있는 원소들의 순서를 뒤집을 수 있음

=> reverse(v.begin(), v.end());

<algorithm> 의 sort도 마찬가지

=> sort(v.begin(), v.end());

6) 예제

vector<int> iv;

vector<pair<int,int>> pv;

 

//사이즈가 3인 vector 생성

vector<int> myv(3);

 

//사이즈가 N(5)이고, 각 원소가 2로 초기화된 vector 생성

int N = 5;

vector<int> myv(N, 2);

 

//vector에 원소 추가

iv.push_back(1);                 // iv : 1

iv.push_back(2);                 // iv : 1 2

iv.push_back(3);                 // iv : 1 2 3

 

pv.push_back(make_pair(2,4));

 

//vector의 size 조정

iv.resize(4);

cout << iv.size();                // 4

 

cout << iv.front();               // 1

cout << iv.back();                // 0 (resize를 4로 했기 때문에 마지막 원소는 자동적으로 0으로 초기화됨)

 

iv.pop_back();                    // iv : 1 2 3

iv.clear();                       // iv : 

3. 11165번 좌표 정렬하기 

- 이 경우 pair를 사용하여 sort 함수를 쓰면

- 자동적으로 pair의 first를 기준으로 정렬하고, first가 같은 경우에는 second를 기준으로 정렬하기 때문에 

- pair 를 사용하면 쉽게 끝낼 수 있다

- 만약에 pair 가 아닌 사용자가 직접 정의한 구조체를 사용한 경우에는 비교함수를 정의해주어야한다 (다음 장에서 다시 설명)

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int main(void) {

int n;

cin >> n;

vector<pair<int,int>> v(n);

for (int i = 0; i < n; i++) {

int x, y;

cin >> x >> y;

v[i] = make_pair(x, y);

}

sort(v.begin(), v.end());

for (int i = 0; i < n; i++) {

cout << v[i].first << " " << v[i].second << endl;

}

return 0;

}