[백준/C++] 11286 절댓값 힙

우선순위 큐(priority_queue)를 사용하는 문제 입니다.

11286번: 절댓값 힙

입력값이 0이 아니라면 추가하고.

입력값이 0이라면 추가된 값들중 절대값이 가장 작은 원소를 출력 후 제거합니다.

원소의 갯수가 없을경우에 0이 입력되면 0을 출력합니다.

 

우선순위큐 priority_queue를 사용하며 구조체 cmp 내부의 operator 함수를 통해서 정렬 구조를 만들어주고난뒤에 입력받은 것을 큐에 push 하여 넣어주고 입력값이 0이라면 큐가 비어있는지 확인 후에 위의 조건을 실행합니다.

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <stack>
#include <map>
#define fastio cin.tie(0)->ios::sync_with_stdio(0); cout.tie(0);
using namespace std;

// 백준 11286 절댓값 힙 (우선순위 큐 문제)

struct cmp // 정렬하려는 기준을 정해주는 구조체
{
	bool operator()(int a, int b) // 연산자
	{
		if (abs(a) == abs(b)) return a > b; // 절대값이 같으면 가장 작은값 반환
		else return abs(a) > abs(b);// 절대값이 작은원소 반환
	}
};

int main() 
{
	fastio;
	int n, x; // 입력 변수
	priority_queue<int, vector<int>, cmp> pq; // 우선순위큐 비교타입 cmp
	vector<int> vec; // 벡터 변수
	cin >> n; // 반복횟수 입력

	for (int i = 0; i < n; i++) // 입력받은 n번만큼 반복
	{
		cin >> x; // 값입력

		if (x == 0) // 입력받은 값이 0일 경우
		{
			if (pq.empty()) // 리스트가 비어있을 경우
				vec.push_back(0); // 벡터에 0 푸시백
			
			else // 리스트가 비어있지 않을경우
			{
				vec.push_back(pq.top()); // 가장작은 원소 푸시백
				pq.pop(); // 푸시한 원소는 제거
			}
		}
		else // 입력받은 값이 0이 아닐경우
		{
			pq.push(x); // 입력한 값 푸시로 추가
		}
	}
	for (int i = 0; i < vec.size(); i++) // 벡터 크기만큼 반복
	{
		cout << vec[i] << "\n"; // 출력하기
	}
	return 0;
}

코드 해석

기본적으로 필요한 헤더와 입출력 속도를 높이는 매크로의 설명은 제외 합니다.

구조체 cmp

struct cmp
{
	bool operator()(int a, int b)
	{
		if (abs(a) == abs(b)) return a > b;
		else return abs(a) > abs(b);
	}
};

위에서 구현된 구조체 cmp는 우선순위 큐에서 사용할 비교(조건)용 구조체 입니다.

operator() 함수를 정의하여 두개의 매개변수 정수를 비교합니다.

함수내부의 조건으로는 절대값(abs())이 같은 경우에는 값이 작은 수가 먼저 오도록 정해줍니다.

즉, 양수를 먼저, 음수를 나중에 놓습니다. ( 큰수 > 작은수 )

만일 매개변수의 절대값이 다를 경우에는 절대값이 작은 수가 먼저 오도록 합니다.

만일 음수와 양수의 비교일 경우에도 절대값은 양수비교가되므로 ( -10 > 1 ) 의 순서가 됩니다.

 

main() 함수

int main() 
{
	fastio;
	int n, x; 
	priority_queue<int, vector<int>, cmp> pq;
	vector<int> vec;
    cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> x;

		if (x == 0)
		{
			if (pq.empty())
				vec.push_back(0);
			
			else
			{
				vec.push_back(pq.top());
				pq.pop();
			}
		}
		else
		{
			pq.push(x);
		}
	}
	for (int i = 0; i < vec.size(); i++)
	{
		cout << vec[i] << "\n";
	}
	return 0;
}

int 형의 n 그리고 x 의 변수는 입력으로 받을 정수를 담기위한 변수 입니다.

 

priority_queue<int, vector<int>, cmp> pq

우선순위 큐를 선언하며, cmp 구조체를 이용하여 정렬 방식을 지정하는 우선순위 큐  pq 입니다.

 

vector<int> vec 는 최종 결과를 저장할 벡터 변수 입니다.

 

이제 총입력받을 숫자의 갯수(n)를 입력받아서 n번만큼의 반복문으로 정수 x를 입력받습니다.

입력받을경우의 조건은 아래와 같습니다.

 

입력된 정수(x)가 숫자 0일경우

우선순위큐(pq)가 비어있을경우(empty()) 0을 벡터 vec에 추가해줍니다.

반대로 비어있지 않을경우 pq 에서 최상위(우선순위큐 조건의 가장높은)를 vec 에 추가한뒤 최상위를 우선순위 큐에서 제거(pop())해줍니다.

 

입력된 정수(x)가 숫자 0이 아닌경우

pq 에 입력된 정수(x)를 삽입(push(x))합니다.

 

위의 반복문이 종료된후에 벡터를 순서대로 모두 출력하면 끝 입니다.

 

정리

이 문제는 입력된 정수를 우선순위 큐를 이용하여 절대값이 작은 순서대로 처리하며,

0이 입력된다면 최소 절대값을 가진 숫자를 출력하고,

그 외의 숫자는 우선순위 큐에 삽입하여,

0이 입력이 될때까지 계속해서 처리하는 작업을 수행합니다.

마지막 출력 결과는 절대값이 작은 순서대로 출력이 됩니다.