거의 알고리즘 일기장

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

알고리즘 문제풀이

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

건우권 2020. 6. 24. 13:53

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

 

1655번: 가운데를 말해요

첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1

www.acmicpc.net

풀이방법

 

풀이 방법은 간단하다!!

 

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으로 자료를 선언하는 우를 범해서 삽질을 좀 했다.ㅠ

반응형

'알고리즘 문제풀이' 카테고리의 다른 글

백준 4195번 _ 친구 네트워크  (0) 2020.06.26
백준 13306번 _ 트리  (0) 2020.06.26
N과 M  (0) 2020.06.24
백준 9251, 9252, 1958 _ LCS 1, 2, 3  (0) 2020.06.17
백준 12852번 _ 1로 만들기 2  (0) 2020.06.13
Comments