백준 11650 C++ 및 vector container, pair, sort, 범위 기반 for문

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

bool compare(pair <int,int> p1, pair <int, int> p2) {
	if (p1.first == p2.first) return p1.second < p2.second; //x좌표가 같다면 y좌표를 통해 순서를 정한다
	return p1.first < p2.first;//x가 같지 않다면 x만으로 순서를 정할 수 있다.
}

int main() {
	int t;
	vector<pair<int, int>> vec;//한 쌍을 변수로 가질 때는 pair로 잡는 것이 좋다
	cin >> t;
	while(t--) {
		int a, b;
		cin >> a >> b;
		vec.push_back(make_pair(a, b));//make_pair 함수를 통해 한 쌍을 만들 수 있다. (a,b)의 한 쌍을 pair로 만든다.
	}

	sort(vec.begin(), vec.end(), compare);

	/*범위 기반 for문*/
	for (auto coor: vec) {
		cout << coor.first << " " << coor.second << "\n";
	}
}

 위 코드는 [좌표 정렬하기] 문제의 정답 코드입니다.

이 문제를 해결하면서 vector, sort, pair, 범위 기반 for문, auto가 사용되어서 많은 공부가 되었습니다.

 

[vector container]

c++의 vector container는 자동으로 메모리가 할당되는 배열로, 기존의 C언어에서 사용했던 배열과도 비슷하며, C언어에서의 사용했던 malloc 동적할당의 장점도 포함되어 있어 매우 유용하게 쓰이는 것 같습니다.

 

*사용법

vector<"데이터타입"> "변수명";   과 같이 선언이 가능합니다.

ex. vector<int> height;//여러 명의 키 정보를 저장하는 height 변수.

배열과 같이 사용되고 원하는 만큼 값을 추가할 수 있습니다.

값을 추가하는 방법은 height.push_back(179); 이런식으로 배열의 맨 뒤 원소에 179를 추가하는 방식으로 값을 추가할 수 있습니다.

 

이 뿐만 아니라 여러 멤버 함수를 사용하는데 간단하게 몇 가지만 알아보겠습니다.

 

*위에서도 사용했던 함수들 begin과 end입니다.

vec.begin()은 vector의 맨 앞 부분을 가리키고, vec.end()는 vector의 맨 뒷 부분을 가리키고 있습니다.

 

*pop

vec.pop_back() 멤버 함수를 사용하면 배열의 맨 마지막에서 pop합니다.

 

이 외에도 유용한 멤버 함수들이 있습니다.

 

[C++ STL sort]

정렬을 해주는 sort함수입니다. 

시간 복잡도는 nlogn이며, intro sort를 사용합니다. intro sort 정렬 방법은 quick sort에 heap sort와 insertion sort를 섞은 방식으로 시간 복잡도는 nlogn입니다.

위 코드에서 보면 sort(vec.begin(), vec.end(), compare)와 같이 사용되었습니다.먼저 sort(vec.begin(), vec.end())부분만 살펴보면 vec의 begin(즉 처음)부터 vec의 end(끝)까지 오름차순으로 정렬을 하겠다는 뜻입니다.

 

그러나 정렬을 할 때 오름차순이 아닌 내림차순으로 해야할 때도 있고, 여러 조건들을 추가해줘야 할 때도 있습니다. 그런 조건들이 필요할 때, 함수를 사용합니다. return 해주는 부분들의 조건이 참일 때 정렬을 합니다. 만약 거짓이라면 정렬을 하지 않습니다.p1.first < p2.first가 참이라면, 즉 전자가 후자보다 작다면 정렬을 합니다.

 

[C++ Pair class]

C++의 Pair 클래스는 한 쌍의 데이터를 관리하기 편합니다. 위 코드처럼 좌표라던지, 데이터가 두 개일 때 사용하면 됩니다.

ex) pair<int, int> p1 = make_pair(5,6); 

이렇게 선언을 한다면 p1점의 x좌표 y좌표를 (5,6)으로 선언할 수 있습니다. make_pair는 한 쌍의 값들을 만들어줍니다. 이 때 여기서 p1.first를 하면 5를 가리키게 되고, p1.second를 하면 6을 가리키게 됩니다.

 

[C++ 범위 기반 for문]

이 for문은 기존 C언어에서는 없었던 새로운 형식의 for문입니다. 기존의 for문과는 달리 범위를 알려주지 않아도 범위를 찾아 반복을 하는 for문입니다.

int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };

	for (int i = 0; i < 10; i++) {
		cout << arr[i];
	}

위와 같이 사용했던 코드를 아래처럼 사용할 수 있습니다.

int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };

	for (int data : arr) {
		cout << data;
	}

int data는 출력할 데이터의 형식을 표현하고 arr는 데이터들을 어디에서 가져올지 쓰면 됩니다. 

 

게시물의 맨 위의 코드에서 auto를 사용했는데 auto는 자동으로 데이터 형식을 설정해주는 것입니다. 자세한 설명은 아래에서 하도록 하겠습니다. 아무튼 자동으로 데이터 형식을 설정하고 vec에 들어있는 값들과 그 크기만큼 순환하면서 출력합니다.

 

이렇게 범위 기반 for문을 사용하여 때로는 더 간략하게 코드를 표현할 수도 있을 것 같습니다.

 

[데이터 타입을 자동으로 설정하는 auto]

auto x = 10; // int

auto y = 12.345; // float

auto z = "hello world!" // string

이렇게하면 x,y,z는 각각 다른  데이터 타입으로 선언이 됩니다. 

즉 auto는 초기화 값에 따라 알아서 데이터 타입을 정해주는 키워드입니다.

 

위 정답코드에서 auto는 pair를 나타내겠네요.

 

 

 

끝까지 읽어주셔서 감사합니다.( _ _ )