[백준/BOJ] 1744. 수 묶기 [Gold 4]

1744. 수 묶기

문제출처 : https://www.acmicpc.net/problem/1744

code

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);

	int x, N, result = 0, i;
	bool zero = false;
	cin >> N; 
	priority_queue<int>minpq;
	priority_queue<int>pluspq;
	queue<int>q;
	
	for (i = 0; i < N; i++)
	{
		cin >> x;
		if (x < 0)
			minpq.push(-x);
		else if (x == 0)
			zero = true;
		else
			pluspq.push(x);
	}

	int min_len = minpq.size();
	int plus_len = pluspq.size();

	/*
	for (i = 0; i < min_len; i++)
	{
		cout << -minpq.top()<< "  ";
		minpq.pop();
	}
	cout << '\n';
	for (i = 0; i < plus_len; i++)
	{
		cout << pluspq.top() << "  ";
		pluspq.pop();
	}
	cout << '\n'<<'\n';
	*/

	//음수연산
	while (minpq.empty()==false)
	{
		int temp;
		temp = -minpq.top();
		minpq.pop();
		if (minpq.empty())
		{
			if (zero == false)
				q.push(temp);
		}
		else
		{
			q.push(temp * -minpq.top());
			minpq.pop();
		}
	}

	//양수연산
	while (pluspq.empty()==false)
	{
		int temp;
		temp = pluspq.top();
		pluspq.pop();
		if (pluspq.empty() || temp == 1)
			q.push(temp);
		else
		{
			if (pluspq.top() == 1)
				q.push(temp);
			else
			{
				q.push(temp * pluspq.top());
				pluspq.pop();
			}
		}
	}

	while (!q.empty())
	{
		result += q.front();
		q.pop();
	}

	cout << result;
	
	return 0;
}

예전에 풀다가 포기한 문제였는데 오늘 다시 찬찬히 풀어보니까 풀렸다. 시간은 좀걸렸지만 이번에는 내 스스로 푼 문제라 조금은 뿌듯하다.

조건이 생각보다 많은데, 처음에 일반 배열로 하니까 너무 복잡해져서 우선순위 큐를 사용했다.
우선순위 큐를 쓰면 해당 조건만 맞춰주면서 푸쉬 팝하니까 쉽게풀린문제였다.