백준 1655번 _ 가운데를 말해요

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

1655번: 가운데를 말해요

풀이방법

 

풀이 방법은 간단하다!!

 

1. BACK과 FOWARD를 multiset의 자료구조로 선언한다.

 

2. input이 들어왔을때 세가지의 조건에 따라 달리 넣어주면된다.

 1. MID값이 비어있을때 

 2. FOWARD.SIZE >= BACK.SIZE 일때

 3. FOWARD.SIZE < BACK.SIZE 일때

 

3. FOWARD의 맨 뒤의 값과 BACK의 맨앞의 값 그리고 MID의 값을 비교해서 적절한 값을 MID로 둔다.

---

코드

#include <iostream>
#include <algorithm>
#include <set>

#define EMPTY 10001

using namespace std;

multiset<int> forwardGroup;
multiset<int> backwardGroup;
int mid = EMPTY;

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

	int N;
	cin >> N;
	
	int inputValue;
	for (int i = 0; i < N; i++)
	{
		cin >> inputValue;
		if (mid == EMPTY)
			mid = inputValue;
		else if (forwardGroup.size() >= backwardGroup.size())
		{
			int insertValue = max(mid, inputValue);
			mid = min(mid, inputValue);
			backwardGroup.insert(insertValue);		
		}
		else
		{
			int insertValue = min(mid, inputValue);
			mid = max(mid, inputValue);
			forwardGroup.insert(insertValue);
		}

		//backward와의 비교
		if (!backwardGroup.empty())
		{
			if (*backwardGroup.begin() < mid)
			{
				backwardGroup.insert(mid);
				mid = *backwardGroup.begin();
				backwardGroup.erase(backwardGroup.begin());
			}
		}
		//forward와의 비교
		if (!forwardGroup.empty())
		{
			if (*(--forwardGroup.end()) > mid)
			{
				forwardGroup.insert(mid);
				mid = *(--forwardGroup.end());
				forwardGroup.erase(--forwardGroup.end());
			}
		}
		
		cout << mid << '\n';
	}

	return 0;
}

---

multiset이 아니라 set으로 자료를 선언하는 우를 범해서 삽질을 좀 했다.ㅠ