Notice
Recent Posts
Recent Comments
Link
거의 알고리즘 일기장
백준 1655번 _ 가운데를 말해요 본문
https://www.acmicpc.net/problem/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으로 자료를 선언하는 우를 범해서 삽질을 좀 했다.ㅠ
반응형
'알고리즘 문제풀이' 카테고리의 다른 글
백준 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