[백준 / BOJ] C++ 1655 가운데를 말해요

https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

풀이

우선순위 큐를 vector에 넣은 후 vector size에 따라 달라지는 값으로 문제를 풀었으나.. 시간초과

for문으로 vector에 입력하는 부분에서 시간초과가 나는것 같습니다.

 

그래서 priority_queue를 max,min 두개를 만들어 주어 중간값을 구하는 방식을 사용했습니다.

중간 값 구하기 알고리즘

1. 최대 힙의 크기는 최소 힙의 크기와 같거나, 하나 더 크다.

2. 최대 힙의 최대 원소는 최소 합의 최소 원소보다 작거나 같다.

이때 알고리즘에 맞지 않다면 최대 힙, 최소 힙의 가장 위의 값을 swap해준다.

https://www.crocus.co.kr/625

[1655번] 가운데를 말해요

참조 사이트입니다.

 

Overtime Code

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

using namespace std;

int main()
{
	int N;
	cin >> N;

	vector <int> vec;
	priority_queue<int> q;

	while (N--)
	{
		int x;
		cin >> x;

		q.push(x);

		for (int i = 0; i < q.size(); i++)
		{
			vec.push_back(q.top());
			q.pop();
		}

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

		if (vec.size() != 0)
		{
			if (vec.size() == 1)
				cout << vec[0] << '\n';
			else if (vec.size() == 2)
			{
				if (vec[0] > vec[1])
				{
					cout << vec[1] << '\n';
				}
				else
					cout << vec[0] << '\n';
			}
			else {
				int CalSize = vec.size() / 2;
				if (vec.size() % 2 == 0)
				{
					if (vec[CalSize - 1] > vec[CalSize])
					{
						cout << vec[CalSize] << '\n';
					}
					else
						cout << vec[CalSize - 1] << '\n';
				}
				else
				{
					if (vec[CalSize] > vec[CalSize + 1])
					{
						cout << vec[CalSize + 1] << '\n';
					}
					else
						cout << vec[CalSize] << '\n';
				}
			}
		}
	}
}

Code

#include<iostream>
#include<queue>

using namespace std;

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

	int N;
	cin >> N;
	priority_queue<int> max;
	priority_queue<int, vector<int>, greater<int>> min;

	while (N--) {
		int a, size;
		cin >> a;
		if (max.size() == min.size()) {
			max.push(a);
		}
		else {
			min.push(a);
		}
		if (!max.empty() && !min.empty() && max.top() > min.top()) {
			int max_val, min_val;
			max_val = max.top();
			min_val = min.top();
			max.pop();
			min.pop();
			max.push(min_val);
			min.push(max_val);


		}
		cout << max.top() << '\n';
	}
}