[C++] 가운데를 말해요 - 1655

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

1655번: 가운데를 말해요

위 사이트에서 문제 내용과 조건등을 읽어오길 바람..!

 

위 문제에서 원하는 답을 출력하기 위해서는

입력 받은 값들 중에서 중간에 위치한 값만 계속 출력해주면 됨

---

가장 먼저 생각해볼 수 있는 방법은 이러함

데이터를 입력받기 -> 배열에 넣기 -> 배열 정렬 -> 가운데 값 출력

 

위의 방법으로도 예제에 해당하는 답들을 출력할 수는 있지만

최대 10만번의 데이터를 입력받는 상황에서 쓸만한 방법은 절대 아님!

입력을 받을 때마다 정렬을 해야하는 상황이기에 nlogn의 속도의 정렬도 안됨..

 

그렇다면 어떤 방법으로 풀어야할까...

---

중간의 값..

우리는 중간에 위치한 값만 출력하면 되기 때문에

굳이굳이 매번 모든 데이터를 완벽하게 정렬할 필요는 없음..!

 

두개의 자료구조를 만들고

한쪽에는 입력받은 값들중에 하위 50%에 해당하는 값들을 밀어놓고 그중에 가장 큰 값을 0번으로

또 한쪽에는 상위 50%에 해당하는 값들을 밀어놓고 그중에 가장 작은 값을 0번으로 만들면

 

아주 빠르게 중간값을 찾을 수 있지 않을까..!? 

이것을 Heap을 이용해서 구현해 보겠음!

 

//TODO 우선순위큐 정리

 

7 - 3 - 1 - 5 - 9 - 10의 값을 입력 받는다고 할때

 

 

첫번째로 maxHeap에 7을 입력받고 그대로 출력!

출력 - 7

---

 

minHeap에 3을 입력 받았지만 maxHeap보다 큰 값을 들고 있어야하기에 데이터 교환

출력 - 7 - 3

---

 

1이 maxHeap에 들어감

출력 - 7 - 3 - 3

---

minHeap에 5가 들어가고 부모노드와 비교 후 5가 더 작으니 자리 바꿈

출력 - 7 - 3 - 3 - 3

---

maxHeap에 9가 입력되고 자리 라트와 자리바꿈

이후 minHeap의 루트노드와 비교 후 자리바꿈

minHeap 서열정리

출력 - 7 - 3 - 3 - 3 - 5

---

10이 입력되고 

출력 - 7 - 3 - 3 - 3 - 5 - 5

 

이렇게하면 매번 logn의 속도로 최소값과 최대값을 구하면서

굉장히 빠른 속도로 중간값을 구할 수 있게 됨

 

소스코드

enum MAXorMIN
{
	// PQ객체 생성시 읽기 편하게 enum으로 만들었음
	MIN = false,
	MAX = true
};

class PQ
{
public:
	PQ(bool b)
	{
		isMAX = b; // true로 하면 maxHeap
	}

	void push(int n)
	{
		v.push_back(n);
        // vector을 사용했지만 배열로 해도 전혀 무방

		int root = static_cast<int>(v.size()) - 1;
		int c = root;

		do
		{ // 부모노드와 비교 후 자리 바꿈
			root = max((c - 1) / 2, 0);
			int rN = v[root];
			int cN = v[c];

			// minHeap, maxHeap을 고려해서 비교함수를 만듦
			if (compare(rN, cN)) 
			{
				v[root] = cN;
				v[c] = rN;
			}
			
			c = root;
		} while (c > 0);
	}
	
    // minHeap과 maxHeap 사이에서 데이터 교환시 사용
	void exChange(int n) 
	{
		if (v.size() == 0) return;

		int size = static_cast<int>(v.size()) - 1;
		
		v[0] = n;

		int c = 0;
		int root = 0;
		
        // 부모와 자식 비교 후 교환
		do
		{
			c = (root * 2) + 1;
			if (c > size) break;

			if (c < size && compare(v[c], v[c+1]))
				c++;

			int rN = v[root];
			int cN = v[c];


			if (c <= size && compare(rN, cN))
			{
				v[root] = cN;
				v[c] = rN;
			}

			root = c;

		} while (root < size);

		
	}

	int top()
	{
		if ((int)v.size() == 0) return -1;
		return v[0];
	}

	bool compare(int r, int c)
	{
		if (isMAX) return r < c; // maxHeap은 큰게 위로
		return r > c; // minHeap은 작은게 위로
	}
	
	int size()
	{
		return static_cast<int>(v.size());
	}

	bool empty()
	{
		return static_cast<int>(v.size()) == 0;
	}

public:
	bool isMAX = false;
	vector<int> v;
};

int main()
{
	ios::sync_with_stdio(false); // 속도 빨라지는 코드
	cin.tie(NULL); // 속도 빨라지는 코드

	vector<int> v;
	int N, n;
	cin >> N;

	PQ max = PQ(MAX);
	PQ min = PQ(MIN);


	for (int i = 0; i < N; i++)
	{
		cin >> n;
		v.push_back(n);
	}



	for (int i = 0; i < N; i++)
	{
		n = v[i];

		if (max.size() == min.size())
			max.push(n); // 작은 값을 내림차순 정렬
		else
			min.push(n); // 큰 값을 오름차순 정렬
		// 그럼 maxHeap과 minHeap의 top값이 가운데 값이 됨

		if (!max.empty() && !min.empty() && max.top() > min.top())
		{
			int maxN, minN;
			maxN = max.top();
			minN = min.top();

			max.exChange(minN);
			min.exChange(maxN);
		}
		cout << max.top() << '\n';
	}

	return 0;
}

소스코드가 이해가 안되면 

디버깅을 해보면서 천천히 살펴보면 좋음