우선순위 큐를 이용한 문제 풀이 - 절댓값 힙 구하기

* Do it 코딩테스트를 참고하였습니다.

 

 해당 문제는 배열의 값들 중 가장 절대값이 작은 값을 출력하고, 해당 값을 제거합니다. 해당 절대값이 여러 개일 경우에는 그 중에서 가장 작은 값을 출력하는 문제입니다.

 

 해당 문제는 반복해서 가장 작은 절대값, 그 중에서도 가장 작은 값을 출력하고 제거하는 방식을 가지고 있습니다. 그렇기 때문에 입력 배열에 대한 정렬이 우선적으로 필요하며, 0이 입력될 때마다 앞에서부터 차례로 제거해나가며 출력한다. 이를 구현하기 위해서 우선순위 큐라는 자료구조를 이용하고자 한다.

 

 우선 순위 큐는 일반적인 큐와 다르게 정렬 기준에 따라서 큐 안에 들어있는 값들을 정렬한다는 특징이 있다. 그렇기 때문에 해당 문제에서 주어진 조건에 맞게 정렬을 하며 값을 넣고 빼며 원하는 값들을 출력할 수 있게 된다.

 

 바로 코드를 살펴보도록 하겠습니다.

struct cmp {
	bool operator()(int L, int R)
	{
		int aR = abs(R);
		int aL = abs(L);

		if (aR != aL)
			return aL > aR;
		else
			return L > R;
	}
};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	priority_queue<int, vector<int>, cmp> Q;
	vector<int> result;
	int count = 0;
	int index = 0;

	for (int i = 0; i < N; i++)
	{
		int temp;
		cin >> temp;

		// 0인 경우
		if (temp == 0)
		{
			//
			if (Q.empty())
			{
				result.push_back(0);
			}
			else
			{
				result.push_back(Q.top());
				Q.pop();
			}
		}
		else
		{
			Q.push(temp);
		}
	}

	for (auto& i : result)
	{
		cout << i << endl;
	}

	return 0;
}

cmp라는 정렬의 기준이 되는 함수를 구조체를 만들어서 우선순위 큐에 값이 추가될 때마다 값을 정렬하고, 0이 입력될 때마다 출력할 값들을 result에 집어넣는 것을 볼 수 있습니다.

 

이것으로 절댓값 힙 구하기 문제에 대한 설명을 마치겠습니다. 포바~!