[Coding Test] Coding Tips 2 : Priority Queue, Bit Operator, etc

삼성B형을 위한 코딩 팁 시리즈

Python 개발자의 PRO 취득을 위한 C++ 공부 여정

• [Coding Test] Coding Tips 1 : ABS(x) macro used in DFS
• [Coding Test] Coding Tips 2 : Priority Queue, Bit Operator
• [Coding Test] Coding Tips 3 : Iterator
• [Coding Test] Coding Tips 4 : algorithm library
• [Coding Test] Coding Tips 5 : 잡-Skill
• [Coding Test] Coding Tips 6 : vector, deque, list
• [Coding Test] Coding Tips 7 : hash

Priority Queue

아래 소스 코드를 통해 두 가지 핵심 요소를 정리할 수 있다.

• struct 연산자 오버로딩
• priority queue custom comparator 사용법

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

struct Point {
	int x, y;

	// 구조체 생성자 선언 (Overloading)
	Point() { x = 0; y = 0; }
	Point(int X, int Y) : x(X), y(Y) {}

	// + operator overloading
	Point operator+(Point a) { return Point(x + a.x, y + a.y); }
	
	// << operator overloading
	friend ostream& operator<<(ostream& os, Point a);
};

// friend
ostream& operator<<(ostream& os, Point a) {
	os << a.x << ' ' << a.y;
	return os;
};

struct CustomComparator {
	bool operator()(Point a, Point b)
	{
		if (a.x == b.x) return a.y < b.y;
		else return a.x < b.x;
	}
};

int main(int argc, char** argv)
{
	priority_queue<Point, vector<Point>, CustomComparator> pq;

	pq.push({ 1,2 });
	pq.push({ 2,4 });
	pq.push({ -1,1 });
	pq.push(Point({ 12, 20 }));
	pq.push(Point({ 8, 10 }));
	pq.push(Point({ 70, 60 }));
	pq.push(Point({ 5, 80}));
	pq.push(Point({ 5, 20 }));
	pq.push(Point(5, 15));
	
	while(!pq.empty())
	{
		cout << pq.top() << '\n';
		pq.pop();
	}

	return 0;
}

이제 하나씩 살펴보자.

struct 연산자 오버로딩

B형 문제들을 풀면서 느낀점이 있다면 자료구조를 정말 잘 짜야한다는 것. 그런데 이렇게 만들어 놓은 자료구조의 기본적인 연산을 정의하기 위해선 아래와 같은 방법을 사용한다. 예를들어, cout << Point 형 구조체 는 사용자가 직접 정의해줘야 하는 것이다.

struct Point {
	int x, y;

	// 구조체 생성자 선언 (Overloading)
	Point() { x = 0; y = 0; }
	Point(int X, int Y) : x(X), y(Y) {}

	// + operator overloading
	Point operator+(Point a) { return Point(x + a.x, y + a.y); }
	
	// << operator overloading
	friend ostream& operator<<(ostream& os, Point a);
};

// friend
ostream& operator<<(ostream& os, Point a) {
	os << a.x << ' ' << a.y;
	return os;
};

위에서는 덧셈과 출력 연산자를 오버로딩했다.

Custom Comparator (비교 연산자)

struct 로 만든 자료구조를 STL 라이브러리 Container 들과 함께 사용하기 위해서는 template 이 요구하는 규칙을 지정해야 한다.

struct CustomComparator {
	bool operator()(Point a, Point b)
	{
		if (a.x == b.x) return a.y < b.y;
		else return a.x < b.x;
	}
};

priority_queue<Point, vector<Point>, CustomComparator> pq;

코딩 테스트 전, 꼭 한 번 확인하고 들어가자. 아니, 이렇게 기억하자.

정렬됐을 때, 오른쪽이 top() 이다.

이를 확인하기 위해 아래 코드를 보자.

 int main(int argc, char** argv)
{
	priority_queue<Point, vector<Point>, CustomComparator> pq;

	pq.push({ 1,2 });
	pq.push({ 2,4 });
	pq.push({ -1,1 });
	pq.push(Point({ 12, 20 }));
	pq.push(Point({ 8, 10 }));
	pq.push(Point({ 70, 60 }));
	pq.push(Point({ 5, 80}));
	pq.push(Point({ 5, 20 }));
	pq.push(Point(5, 15));
	
	while(!pq.empty())
	{
		cout << pq.top() << '\n';
		pq.pop();
	}

	return 0;
}

코드가 보여주는 결과는 오름차순 정렬 논리를 사용했을 때, 가장 오른쪽의 원소들부터 top() 에 나타나는 모습이다. 이를 잘 기억해 두도록 하자.

70 60
12 20
8 10
5 80
5 20
5 15
2 4
1 2
-1 1